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

©2024 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(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.

Zmienne pomocnicze:

i : długość prefiksu łańcucha s, i ∈ N.
n : długość łx 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, ; 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

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 <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;
}
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
Python (dodatek)
# 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()
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ę 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 :  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 :   AA 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 AA 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|: ; 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

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 <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;
}
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
Python (dodatek)
# Wyznaczanie maksymalnego PS
# Data:  6.03.2024
# (C)2020 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

PI = [-1]
b = -1
for i in range(1,41):
    while (b > -1) and (s[b]!=s[i-1]):
        b = PI[b]
    b += 1
    PI.append(b)
print(b)
print()

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
©2024 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.