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 oraz 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.

Elementy 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 ; na końcu dołączamy wartownika
K02: p_max ← -1 ; inicjujemy zmienne
K03: l_max ← 0
K04: l_m ← 0
K05: Dla i = 0, 1, …, |s|-1: ; przeglądamy kolejne znaki łańcucha
     wykonuj kroki K06…K14
K06:   Jeśli s[i] = znak_słowa
       to idź do kroku K12
K07:   Jeśli l_m ≤ l_max, 
       to idź do kroku K10
K08:   l_max ← l_m ; zapamiętujemy długość słowa
K09:   p_max← p_m ; i jego pozycję w łańcuchu
K10:   l_m ← 0 ; zerujemy licznik długości
K11:   Następny obieg pętli K05
K12:   Jeśli l_m = 0, ; zapamiętujemy pozycję
       to p_m ← i     ; początku słowa
K13:   l_m ← l_m+1 ; zwiększamy długość słowa
K14: Zakończ zwracając 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" << endl;
  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

Python (dodatek)

# Wyszukiwanie najdłuższego słowa
# Data: 14.03.2024
# (C)2024 mgr Jerzy Wałaszek
# -------------------------------

pm = 0
s = input()
s += " " # dodajemy wartownika
n = len(s)
x = "AĄBCĆDEĘFGHIJKLŁMNOÓPQRSŚTUVWXYZŻŹ"
x += x.lower()
x += "_-0123456789"
pmax, lmax, lm = -1, 0, 0
for i in range(n):
    if x.find(s[i]) > -1:
        if not lm:
            pm = i;
        lm += 1
    else:
        if lm > lmax:
            lmax, pmax = lm, pm
        lm = 0
if pmax == -1:
    print("BRAK")
else:
    print("[%s] : %d" % (s[pmax:pmax+lmax], lmax))
print()

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