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


Tematy pokrewne
Łańcuchy znakowe
Podstawowe pojęcia dotyczące przetwarzania tekstów
Podstawowe operacje na łańcuchach znakowych
Naiwne wyszukiwanie wzorca w tekście
Wyszukiwanie maksymalnego prefikso-sufiksu
Szybkie wyszukiwanie wzorca algorytmem Morrisa-Pratta
Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta
Szybkie wyszukiwanie wzorca uproszczonym algorytmem Boyera-Moore'a
Szybkie wyszukiwanie wzorca pełnym algorytmem Boyera-Moore'a
Wyszukiwanie wzorca algorytmem Karpa-Rabina
Zliczanie słów w łańcuchu
Dzielenie łańcucha na słowa
Wyszukiwanie najdłuższego słowa w łańcuchu
Wyszukiwanie najdłuższego wspólnego podłańcucha
Wyszukiwanie najdłuższego wspólnego podciągu
Wyszukiwanie najkrótszego wspólnego nadłańcucha
Wyszukiwanie słów podwójnych
Wyszukiwanie palindromów
MasterMind – komputer kontra człowiek
MasterMind – człowiek kontra komputer
Szyfr Cezara
Szyfrowanie z pseudolosowym odstępem
Szyfry przestawieniowe
Szyfr Enigmy
Szyfrowanie RSA
Dodawanie dużych liczb
Mnożenie dużych liczb
Potęgowanie dużych liczb
Duże liczby Fibonacciego
Haszowanie
Podstawowe operacje na tablicach
Wyszukiwanie liniowe
Wyszukiwanie liniowe z wartownikiem
Wyszukiwanie max lub min

 

Problem

W łańcuchu s znaleźć 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 pmax w łańcuchu s oraz liczba znaków lmax w tym słowie. Jeśli pmax 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.
pm  – pozycja początku słowa, pm C.
lm  – liczba znaków w słowie, lm C.
Lista kroków:
K01: ss + wartownik ; dołączamy wartownika
K02: pmax ← -1 ; inicjujemy zmienne
K03: lmax ← 0  
K04: lm ← 0  
K05: Dla i = 0, 1,...,|s| - 1, wykonuj K06...K14 ; przeglądamy kolejne znaki łańcucha
K06:     Jeśli s[i] = litera_lub_cyfra, to idź do K12 ; znak należący do słowa?
K07:     Jeśli lmlmax, to idź do K10 ; dłuższe słowo niż  dotychczas zapamiętane?
K08:     lmaxlm ; jeśli tak, to zapamiętujemy go
K09:     pmaxpm  
K10:     lm ← 0 ; po zapamiętaniu, zerujemy długość słowa
K11:     Następny obieg pętli K05  
K12:     Jeśli lm > 0, to idź do K15 ; początek słowa?
K13:     pm i ; jeśli tak, to zapamiętujemy pozycję pierwszego znaku
K14:     lm lm + 1 ; a długość ustawiamy na 1
K15 Zakończ z wynikiem pmax i lmax  

 

Program

Ważne:

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.

 

Lazarus
// Wyszukiwanie najdłuższego słowa
// Data:  9.07.2008
// (C)2012 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.
Code::Blocks
// Wyszukiwanie najdłuższego słowa
// Data:  9.07.2008
// (C)2012 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;
}
Free Basic
' Wyszukiwanie najdłuższego słowa
' Data:  9.07.2008
' (C)2012 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)2012 mgr Jerzy Wałaszek

Wprowadź tekst:


...

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.