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 ² ), jednakże dla typowych tekstów pracuje w czasie prawie liniowym O ( n  ).

Algorytm naiwny wyszukiwania maksymalnego prefikso-sufiksu

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

// 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;
}

' 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

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.

s  :   A B A C A B A B 
i  : 0 1 2 3 4 5 6 7 8
Π [ ] :-1 ? ? ? ? ? ? ? ?

s  :   A B A C A B A B
i  : 0 1 2 3 4 5 6 7 8
Π [ ] :-1 0 ? ? ? ? ? ? ?

s  :   A B A C A B A B
i  : 0 1 2 3 4 5 6 7 8
Π [ ] :-1 0 0 ? ? ? ? ? ?

s  :   A B A C A B A B
i  : 0 1 2 3 4 5 6 7 8
Π [ ] :-1 0 0 1 ? ? ? ? ?

s  :   A B A C A B A B
i  : 0 1 2 3 4 5 6 7 8
Π [ ] :-1 0 0 1 0 ? ? ? ?

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 ? ? ?

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 ? ?

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 ?

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 

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

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

// 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; 
}

' 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