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

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Wyszukiwanie maksymalnego prefikso-sufiksu

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Problem

Dla danego łańcucha s  należy 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 ( n 2 ), 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.

Zmienne 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: i  ← n  - 1 rozpoczynamy od maksymalnego prefiksu
K03: Dopóki i  > 0,
wykonuj kroki K04...K05
szukamy maksymalnego prefikso-sufiksu
K04:     Jeśli s [ 0 : i  ] = s [ n  - i  : n  ],
    to idź do kroku K06
sprawdzamy, czy prefiks jest równy sufiksowi
K05:     i  ← i  - 1 następny, mniejszy prefiks
K06: Zakończ z wynikiem i  

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 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ść.
Pascal
// Wyznaczanie maksymalnego PS
// Data:   1.06.2008
// (C)2020 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.
C++
// Wyznaczanie maksymalnego PS
// Data:   1.06.2008
// (C)2020 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;
}
Basic
' Wyznaczanie maksymalnego PS
' Data:   1.06.2008
' (C)2020 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)2020 mgr Jerzy Wałaszek


...

Na początek:  podrozdziału   strony 

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:

obrazek

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.

obrazek

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:

obrazek

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

obrazek

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

obrazek

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

obrazek

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.

Zmienne pomocnicze:

Π  –  tablica długości prefikso-sufiksów kolejnych prefiksów łańcucha s. Indeksy od 0 do | s |. Elementy Π  ∈ 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 kroki 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:     b  ← b  + 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  

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 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ść.
Pascal
// Wyznaczanie maksymalnego PS
// Data:  1.06.2008
// (C)2020 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.
C++
// Wyznaczanie maksymalnego PS
// Data:  1.06.2008
// (C)2020 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; 
}
Basic
' Wyznaczanie maksymalnego PS
' Data:  1.06.2008
' (C)2020 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
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
©2020 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.