Wyszukiwanie maksymalnego prefikso-sufiksu


Tematy pokrewne   Podrozdziały
Ł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
Wbudowane generatory liczb pseudolosowych
Generowanie liczb pseudolosowych
Liczby Fibonacciego
Podstawowe operacje na tablicach
Wyszukiwanie liniowe
Wyszukiwanie liniowe z wartownikiem
  Rozwiązanie 1
Rozwiązanie 2

 

Problem

Dla danego łańcucha s wyznaczyć maksymalny prefikso-sufiks.

 

 

Zadanie wyszukania w łańcuchu s maksymalnego prefikso-sufiksu sprowadza się do znalezienia najdłuższego prefiksu, który jednocześnie jest sufiksem łańcucha s.

 

Rozwiązanie nr 1

Pierwsze rozwiązanie uzyskamy wykorzystując bezpośrednio definicję prefikso-sufiksu. Rozpoczynamy od maksymalnego prefiksu właściwego. Następnie porównujemy kolejne, coraz mniejsze prefiksy z sufiksami aż do uzyskania zgodności lub do otrzymania pustego prefiksu. W obu przypadkach zwracamy długość prefiksu, na którym zakończyliśmy porównywanie.

Algorytm posiada złożoność O(n2), jednakże dla typowych tekstów pracuje w czasie prawie liniowym O(n).

 

Algorytm naiwny wyszukiwania maksymalnego prefikso-sufiksu

Wejście
s  –  łańcuch znakowy
Wyjście:

długość maksymalnego prefikso-sufiksu łańcucha s.

Elementy pomocnicze:
i  –  długość prefiksu łańcucha s, i N
n  – długość łańcucha s, n N
Lista kroków:
K01: n ← |s| ; obliczamy długość łańcucha s
K02: in - 1 ; rozpoczynamy od maksymalnego prefiksu
K03: Dopóki i > 0  wykonuj K04...K05 ; szukamy maksymalnego prefikso-sufiksu
K04:     Jeśli s[0 : i] = s[n - i : n], to idź do K06 ; sprawdzamy, czy prefiks jest równy sufiksowi
K05:     ii - 1 ; następny, mniejszy prefiks
K06: Zakończ z wynikiem i  

 

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 generuje 40 znakowy łańcuch zbudowany z pseudolosowych kombinacji liter A i B. Następnie wyznacza w tym łańcuchu maksymalny prefikso-sufiks i podaje jego długość.

 

Lazarus
// Wyznaczanie maksymalnego PS
// Data:   1.06.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

program prg;

var
  s : ansistring;
  i,n : integer;

begin
  randomize;

  // generujemy łańcuch

  s := '';
  for i := 1 to 40 do s := s + chr(65 + random(2));

  // wypisujemy łańcuch

  writeln(s);

  // szukamy prefikso-sufiksu

  n := length(s);
  i := n - 1;
  while i > 0 do
  begin
    if copy(s,1,i) = copy(s,n - i + 1,i) then break;
    dec(i);
  end;
  writeln(i); 
  writeln;
end.
Code::Blocks
// Wyznaczanie maksymalnego PS
// Data:   1.06.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <time.h>

using namespace std;

int main()
{
  string s;
  int i,n;

  srand((unsigned)time(NULL));

  // generujemy łańcuch

  s = "";
  for(i = 0; i < 40; i++) s += 65 + rand() % 2;

  // wypisujemy łańcuch

  cout << s << endl;

  // szukamy prefikso-sufiksu

  n = s.length();
  for(i = n - 1; i > 0; i--) if(s.substr(0,i) == s.substr(n - i,i)) break;
  cout << i << endl << endl;
  return 0;
}
Free Basic
' Wyznaczanie maksymalnego PS
' Data:   1.06.2008
' (C)2012 mgr Jerzy Wałaszek
'-----------------------------

Dim s As String
Dim As Integer i,n

Randomize

' generujemy łańcuch

s = ""
For i = 1 To 40: s += Chr(65 + Cint(Rnd * 1)): Next

' wypisujemy łańcuch

Print s

' szukamy prefikso-sufiksu

n = Len(s)
i = n - 1
While i > 0
  If Mid(s,1,i) = Mid(s,n - i + 1,i) Then Exit While
  i -= 1
Wend
Print i 
Print
End
Wynik
ABBAAABBBAAAAABBABAABAABABBBABABBABBABBA
4

 

Wyszukiwanie maksymalnego prefikso-sufiksu
(C)2012 mgr Jerzy Wałaszek


...

 

Rozwiązanie nr 2

Podany w rozwiązaniu nr 1 algorytm można znacząco ulepszyć wykorzystując programowanie dynamiczne oraz proste własności prefikso-sufiksów. Postaraj się dokładnie zrozumieć podane poniżej informacje – najlepiej tę partię rozdziału przeczytaj kilkakrotnie. Przyda ci się to przy algorytmach MP i KMP.

Własność 1 – rozszerzenie prefikso-sufiksu

Jeśli maksymalny prefiks właściwy łańcucha tekstowego s posiada prefikso-sufiks o długości k znaków:

 

 

to powiemy, iż prefikso-sufiks prefiksu jest rozszerzalny do prefikso-sufiksu całego łańcucha s, jeśli znak s[k] (czyli znak leżący tuż za prefiksem należącym do prefikso-sufiksu) jest równy znakowi s[n-1] (czyli znakowi leżącemu tuż za sufiksem należącym do prefikso-sufiksu). Wtedy długość prefikso-sufiksu zwiększa się do k + 1 i staje się on prefikso-sufiksem łańcucha s.

 

 

Własność 2 – redukcja prefikso-sufiksu

Jeśli łańcuch tekstowy s posiada prefikso-sufiks, a ten prefikso-sufiks również posiada swój własny prefikso-sufiks, to jest on także prefikso-sufiksem łańcucha s. Brzmi zawile, lecz uzasadnienie jest bardzo proste:

 

Łańcuch tekstowy s posiada prefikso-sufiks b:

 

Prefikso-sufiks b posiada swój własny prefikso-sufiks bb:

 

Ponieważ b jest jednocześnie prefiksem i sufiksem łańcucha s:

 

to jego prefikso-sufiks bb jest również prefikso-sufiksem łańcucha s:

 

Co więcej, jeśli prefikso-sufiks b był maksymalnym prefikso-sufiksem łańcucha s, a prefikso-sufiks bb był maksymalnym prefikso-sufiksem prefikso-sufiksu b, to nowy prefikso-sufiks bb jest poprzednim prefikso-sufiksem łańcucha s. Pomiędzy prefikso-sufiksem b i bb nie istnieje żaden inny prefikso-sufiks łańcucha s.

 

Z programowaniem dynamicznym (ang. dynamic programming) zetknęliśmy się już przy okazji wyliczania kolejnych liczb ciągu Fibonacciego. Polega ono na rozwiązywaniu problemu głównego startując od problemów najprostszych. Rozwiązania zapamiętujemy i z nich tworzymy rozwiązania problemów na wyższym poziomie. Proces ten kontynuujemy aż do osiągnięcia rozwiązania problemu docelowego.

Podane powyżej dwie własności pozwalają wyznaczyć pomocniczą tablicę maksymalnych prefikso-sufiksów dla kolejnych prefiksów łańcucha tekstowego s (pierwsza własność umożliwia rozszerzenie prefikso-sufiksu dla kolejnego prefiksu, jeśli znamy prefikso-sufiks poprzedniego prefiksu, a druga własność pozwala szukać prefikso-sufiksów, które mogą być rozszerzane, jeśli bieżącego prefikso-sufiksu nie można rozszerzyć). Tablica ta nosi zwykle nazwę Π (niekiedy spotyka się nazwę MPNext – od nazwisk twórców algorytmu – Morrisa i Pratta). Indeks w tablicy Π oznacza długość prefiksu łańcucha s, natomiast element o tym indeksie ma wartość długości maksymalnego prefikso-sufiksu dla danego prefiksu. Na przykład, jeśli Π[6] = 2, to prefiks 6-cio znakowy łańcucha s posiada prefikso-sufiks maksymalny o długości dwóch znaków.

Jeśli łańcuch s składa się z m znaków, to indeksy tablicy Π mają wartości od 0 do m, Zerowy element tablicy ma zawsze wartość równą -1 i pełni funkcję wartownika. Nie pozwala on wyjść poza prefiks pusty przy przeglądaniu wstecznym tablicy Π.

 

Przykład:

Wyznaczymy tablicę Π dla łańcucha ABACABAB.

Lp. Tworzona tablica Π Opis
1.
s  :   A B A C A B A B 
i  : 0 1 2 3 4 5 6 7 8
Π[]:-1 ? ? ? ? ? ? ? ?
Element Π[0] jest zawsze równy -1. Pełni on rolę wartownika, dzięki któremu upraszcza się algorytm wyznaczania kolejnych elementów tablicy.
2.
s  :   A B A C A B A B
i  : 0 1 2 3 4 5 6 7 8
Π[]:-1 0 ? ? ? ? ? ? ?
Prefiks jednoznakowy A posiada zawsze prefikso-sufiks pusty, ponieważ prefikso-sufiks musi się składać z prefiksu i sufiksu właściwego. Zatem Π[1] = 0.
3.
s  :   A B A C A B A B
i  : 0 1 2 3 4 5 6 7 8
Π[]:-1 0 0 ? ? ? ? ? ?
Prefikso-sufiks prefiksu dwuznakowego AB ma szerokość 0.  Π[2] = 0.
4.
s  :   A B A C A B A B
i  : 0 1 2 3 4 5 6 7 8
Π[]:-1 0 0 1 ? ? ? ? ?
Prefiks trójznakowy ABA ma prefikso-sufiks maksymalny o szerokości 1, który obejmuje pierwszą i ostatnią literkę A. Π[3] = 1.
5.
s  :   A B A C A B A B
i  : 0 1 2 3 4 5 6 7 8
Π[]:-1 0 0 1 0 ? ? ? ?
Prefiks czteroznakowy ABAC znów posiada prefikso-sufiks pusty o szerokości 0. Π[4] = 0.
6.
s  :   A B A C A B A B
i  : 0 1 2 3 4 5 6 7 8
Π[]:-1 0 0 1 0 1 ? ? ?
Prefiks pięcioznakowy ABACA posiada maksymalny prefikso-sufiks o szerokości 1, obejmujący pierwszą i ostatnią literkę A. Π[5] = 1.
7.
s  :   A B A C A B A B
i  : 0 1 2 3 4 5 6 7 8
Π[]:-1 0 0 1 0 1 2 ? ?
Prefikso-sufiks prefiksu sześcioznakowego ABACAB jest rozszerzeniem prefikso-sufiksu poprzedniego prefiksu. Zatem Π[6] = 2.
8.
s  :   A B A C A B A B
i  : 0 1 2 3 4 5 6 7 8
Π[]:-1 0 0 1 0 1 2 3 ?
Prefikso-sufiks prefiksu siedmioznakowego ABACABA również jest rozszerzeniem prefikso-sufiksu prefiksu poprzedniego, czyli Π[7] = 3.
9.
s  :   A B A C A B A B 
i  : 0 1 2 3 4 5 6 7 8 
Π[]:-1 0 0 1 0 1 2 3 2 
W tym przypadku prefikso-sufiks niewłaściwego prefiksu wzorca ABACABAB nie jest rozszerzeniem prefikso-sufiksu prefiksu poprzedniego. Sprawdzamy zatem, czy nie można rozszerzyć wewnętrznego prefikso-sufiksu tego prefikso-sufiksu - zaznaczyliśmy go niebieskim kolorem. Szerokość prefikso-sufiksu wewnętrznego otrzymamy zawsze ze wzoru:

szerokość prefikso-sufiksu wewnętrznego = Π[szerokość prefikso-sufiksu poprzedniego]

Jeśli poprzedni prefiks miał prefikso-sufiks o szerokości 3, to wewnętrzny prefikso-sufiks ma szerokość: Π[3] = 1. Jak widzimy, ten wewnętrzny prefikso-sufiks jest rozszerzalny do prefikso-sufiksu o szerokości 2. Zatem Π[8] = 2.

 

Ostatni element tablicy Π jest maksymalnym prefikso-sufiksem łańcucha s. Wyznaczenie zawartości tablicy Π dla łańcucha s zbudowanego z m znaków ma liniową klasę złożoności obliczeniowej równą O(m).

 

Algorytm Morrisa-Pratta wyszukiwania maksymalnego prefikso-sufiksu

Wejście
s  –  łańcuch znakowy
Wyjście:

długość maksymalnego prefikso-sufiksu łańcucha s.

Elementy pomocnicze:
Π  –  tablica długości prefikso-sufiksów kolejnych prefiksów łańcucha s. Indeksy od 0 do |s|.Π C
b  – długość prefikso-sufiksu, b C
i  – indeks, i N
Lista kroków:
K01: Π[0] ← -1 ; na początku tablicy Π wstawiamy wartownika
K02: b ← -1 ; początkowo długość prefikso-sufiksu ustawiamy na -1
K03: Dla i = 1,2,...,|s| wykonuj K04...K06 ; wyznaczamy długości prefikso-sufiksów dla prefiksów łańcucha s
K04:     Dopóki b > -1 ∧ s[b] ≠ s[i - 1],
    wykonuj b ← Π[b]
; pętla K04 przerywa się w dwóch przypadkach:
; - szerokość prefikso-sufiksu b osiągnęła wartownika
; - prefikso-sufiks poprzedniego prefiksu jest rozszerzalny
; w przeciwnym razie prefikso-sufiks jest redukowany do swojego
; prefikso-sufiksu i pętla się powtarza
K05:     bb + 1 ; W tym kroku znajdujemy się z wartością b = -1,  gdy prefikso-sufiksu
; nie da się rozszerzyć, lub z b = długości rozszerzalnego
; prefikso-sufiksu poprzedniego prefiksu.
; W obu przypadkach zwiększenie b o 1 daje poprawną wartość
; wpisu do tablicy Π.
K06:     Π[i] ← b ; szerokość prefiksosufiksu prefiksu zapamiętujemy w tablicy
K07: Zakończ z wynikiem b  

 

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 generuje 40 znakowy łańcuch zbudowany z pseudolosowych kombinacji liter A i B. Następnie wyznacza w tym łańcuchu maksymalny prefikso-sufiks i podaje jego długość.

 

Lazarus
// Wyznaczanie maksymalnego PS
// Data:  1.06.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

program prg;

var
  s : ansistring;
  PI : array[0..40] of integer;
  i,b : integer;

begin
  randomize;

  // generujemy łańcuch

  s := '';
  for i := 1 to 40 do s := s + chr(65 + random(2));

  // wypisujemy łańcuch

  writeln(s);

  // szukamy prefikso-sufiksu

  PI[0] := -1; b := -1;
  for i := 1 to 40 do
  begin
    while (b > -1) and (s[b + 1] <> s[i]) do b := PI[b];
    inc(b); PI[i] := b;
  end;
  writeln(b); 
  writeln;
end.
Code::Blocks
// Wyznaczanie maksymalnego PS
// Data:  1.06.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <time.h>

using namespace std;

int main()
{
  string s;
  int PI[41],i,b;

  srand((unsigned)time(NULL));

  // generujemy łańcuch

  s = "";
  for(i = 0; i < 40; i++) s += 65 + rand() % 2;

  // wypisujemy łańcuch

  cout << s << endl;

  // szukamy prefikso-sufiksu

  PI[0] = b = -1;
  for(i = 1; i <= 40; i++)
  {
    while((b > -1) && (s[b] != s[i - 1])) b = PI[b];
    PI[i] = ++b;
  }
  cout << b << endl << endl; 
  return 0; 
}
Free Basic
' Wyznaczanie maksymalnego PS
' Data:  1.06.2008
' (C)2012 mgr Jerzy Wałaszek
'-----------------------------

Dim s As String
Dim As Integer PI(40),i,b

Randomize

' generujemy łańcuch

s = ""
For i = 1 To 40: s += Chr(65 + Cint(Rnd)): Next

' wypisujemy łańcuch

Print s

' szukamy prefikso-sufiksu

PI(0) = -1: b = -1
For i = 1 To 40
  While (b > -1) And (Mid(s,b + 1,1) <> Mid(s,i,1)): b = PI(b): Wend
  b += 1: PI(i) = b
Next
Print b
Print
End

 



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.