Algorytmy i Struktury Danych - Najdłuższe słowo

Najdłuższe słowo łańcucha (ang. the longest word of s string ) s możemy znaleźć w czasie liniowym O ( n ) wykorzystując nieco zmodyfikowany algorytm podziału łańcucha na słowa działający zgodnie z algorytmem znajdowania wartości maksymalnej w zbiorze. Zasada jest następująca:

Przeglądamy łańcuch s wydobywając z niego słowa. W trakcie tego procesu obliczamy liczbę znaków w każdym z wydobytych słów. Liczby te tworzą zbiór, w którym wyszukujemy element maksymalny. Zapamiętujemy pozycję pierwszego znaku słowa raz jego długość.

Algorytm wyszukiwania najdłuższego słowa w łańcuchu

Wejście:

s – łańcuch tekstowy.

Wyjście:

Pozycja pierwszego znaku najdłuższego słowa p_max w łańcuchu s oraz liczba znaków l_max w tym słowie. Jeśli p_max jest równe -1, to łańcuch s nie zawiera żadnego słowa.

Zmienne pomocnicze:

i	–	indeks znaków w łańcuchu s, i ∈ N.
p_m	–	pozycja początku słowa, p_m ∈ C.
l_m	–	liczba znaków w słowie, l_m ∈ C.

Lista kroków:

K01:	s ← s + wartownik	dołączamy wartownika
K02:	p_max ← -1	inicjujemy zmienne
K03:	l_max ← 0
K04:	l_m ← 0
K05:	Dla i = 0, 1, ..., \| s \| - 1: wykonuj kroki K06...K14	przeglądamy kolejne znaki łańcucha
K06:	Jeśli s [ i ] = litera_lub_cyfra, to idź do kroku K12	znak należący do słowa?
K07:	Jeśli l_m ≤ l_max, to idź do kroku K10	dłuższe słowo niż dotychczas zapamiętane?
K08:	l_max ← l_m	jeśli tak, to zapamiętujemy go
K09:	p_max ← p_m
K10:	l_m ← 0	po zapamiętaniu, zerujemy długość słowa
K11:	Następny obieg pętli K05
K12:	Jeśli l_m > 0, to idź do kroku K15	początek słowa?
K13:	p_m ← i	jeśli tak, to zapamiętujemy pozycję pierwszego znaku
K14:	l_m ← l_m + 1	a długość ustawiamy na 1
K15	Zakończ z wynikiem p_max i l_max

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje wiersz znaków i wypisuje najdłuższe, zawarte w nim słowo oraz liczbę znaków w tym słowie. Jeśli łańcuch nie zawiera żadnego słowa, pojawia się napis BRAK.

Pascal

// Wyszukiwanie najdłuższego słowa
// Data:  9.07.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

program prg;

var
  s : ansistring;
  i, pmax, lmax, pm, lm: integer;

begin
  readln ( s );
  s := s + ' '; // dodajemy wartownika
  pmax := -1; lmax := 0; lm := 0;
  for i := 1 to length ( s ) do
    if s [ i ] in [ '0'..'9', '_', '-', 
                    'A'..'Z', 'a'..'z', 
                    'Ą', 'ą', 'Ć', 'ć', 'Ę', 'ę', 
                    'Ł', 'ł', 'Ń', 'ń', 'Ó', 'ó', 
                    'Ś', 'ś', 'Ź', 'ź', 'Ż', 'ż' ] then
    begin
      if lm = 0 then pm := i;
      inc ( lm );
    end
    else
    begin
      if lm > lmax then
      begin
        lmax := lm; pmax := pm;
      end;
      lm := 0;
    end;
  if pmax = -1 then writeln ( 'BRAK' )
  else              writeln ( ' [ ', copy ( s, pmax, lmax ), ' ] : ', lmax );
  writeln;
end.

C++

// Wyszukiwanie najdłuższego słowa
// Data:  9.07.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>

using namespace std;

int main( )
{
  string s;
  int i, pmax, lmax, pm, lm, n;
  unsigned char c;

  getline ( cin, s );
  s += " "; // dodajemy wartownika
  n = s.length( );
  pmax = -1; lmax = lm = 0;
  for( i = 0; i < n; i++ )
  {
    c = s [ i ];
    if( ( ( c >= '0' ) && ( c <= '9' ) ) || 
          ( c == '_' ) || ( c == '-' )   ||
        ( ( c >= 'A' ) && ( c <= 'Z' ) ) ||
        ( ( c >= 'a' ) && ( c <= 'z' ) ) ||
          ( c == 164 ) || ( c == 165 )   ||
          ( c == 143 ) || ( c == 134 )   ||
          ( c == 168 ) || ( c == 169 )   ||
          ( c == 157 ) || ( c == 136 )   ||
          ( c == 227 ) || ( c == 228 )   ||
          ( c == 224 ) || ( c == 162 )   ||
          ( c == 151 ) || ( c == 152 )   ||
          ( c == 141 ) || ( c == 171 )   ||
          ( c == 189 ) || ( c == 190 ) )
    {
      if( !lm ) pm = i;
      lm++;
    }
    else
    {
      if( lm > lmax )
      {
        lmax = lm; pmax = pm;
      }
      lm = 0;
    }
  }
  if( pmax == -1 ) cout << "BRAK\n";
  else cout << " [ " << s.substr ( pmax, lmax ) << " ] : " << lmax << endl;
  cout << endl;
  return 0;
}

Basic

' Wyszukiwanie najdłuższego słowa
' Data:  9.07.2008
' (C)2020 mgr Jerzy Wałaszek
'-----------------------------

Dim As String s
Dim As Integer i, pmax, lmax, pm, lm, n, c

Line Input s
s += " " 'dodajemy wartownika
n = Len ( s )
pmax = -1: lmax = 0: lm = 0
For i = 1 To n
  c = Asc ( Mid ( s, i, 1 ) )
  if( ( ( c >= Asc ( "0" ) ) And ( c <= Asc ( "9" ) ) ) Or ( c = Asc ( "_" ) )  Or ( c = Asc ( "-" ) )        Or _
      ( ( c >= Asc ( "A" ) ) And ( c <= Asc ( "Z" ) ) ) Or ( ( c >= Asc ( "a" ) ) And ( c <= Asc ( "z" ) ) )  Or _
        ( c = 164 ) Or ( c = 165 )  Or ( c = 143 ) Or ( c = 134 )  Or ( c = 168 ) Or ( c = 169 )  Or _
        ( c = 157 ) Or ( c = 136 )  Or ( c = 227 ) Or ( c = 228 )  Or ( c = 224 ) Or ( c = 162 )  Or _
        ( c = 151 ) Or ( c = 152 )  Or ( c = 141 ) Or ( c = 171 )  Or ( c = 189 ) Or ( c = 190 ) ) Then
    If lm = 0 Then pm = i
    lm += 1
  Else
    If lm > lmax Then
      lmax = lm: pmax = pm
    End If
    lm = 0
  End If
Next
If pmax = -1 Then
  Print "BRAK"
Else
  Print " [ ";Mid ( s, pmax, lmax );" ] : ";lmax
End If
Print
End

Wynik:

Wielki mały cały śmiały człowiek szybki i gibki
[ człowiek ] : 8

Na początek: podrozdziału strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Wyszukiwanie najdłuższego słowa w łańcuchu