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

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

Przykładowe programy

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

using namespace std;

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

  srand(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

# Wyznaczanie maksymalnego PS
# Data:   6.03.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random

# generujemy łańcuch
s = "";
for i in range(40):
    s += chr(random.randrange(65, 67))
# wypisujemy łańcuch
print(s)
# szukamy prefikso-sufiksu
n = len(s)
for i in reversed(range(n)):
    if s[:i] == s[n-i:]: break;
print(i)
print()

ABBAAABBBAAAAABBABAABAABABBBABABBABBABBA
4

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

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|: ; wyznaczamy długości prefikso-sufiksów
     wykonuj kroki K04…K06 ; 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

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

using namespace std;

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

  srand(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

# Wyznaczanie maksymalnego PS
# Data:  6.03.2024
# (C)2020 mgr Jerzy Wałaszek
#---------------------------

import random

# Długość łańcucha
N = 40
# Generujemy łańcuch
s = ""
for i in range(N):
    s += chr(random.randrange(65, 67))
# Wypisujemy łańcuch
print(s)
# Szukamy prefikso-sufiksu
tpi = [-1]
b = -1
for i in range(N):
    while (b > -1) and (s[b] != s[i]):
        b = tpi[b]
    b += 1
    tpi.append(b)
print(b)
print()