Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2022 mgr Jerzy Wałaszek
I LO w Tarnowie

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

SPIS TREŚCI
Tematy pomocnicze

Problem

W łańcuchu s  należy znaleźć najdłuższe słowo.

Rozwiązanie

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
Wyszukiwanie najdłuższego słowa
(C)2020 mgr Jerzy Wałaszek

Wprowadź tekst:

...

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2022 mgr Jerzy Wałaszek

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.