Algorytmy i Struktury Danych - Wyszukiwanie maksymalnego prefikso-sufiksu

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

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

JavaScript

<html>
  <head>
    <title>
      PS
    </title>
  </head>
  <body>

<div style="overflow-x: auto;"
     align="center">
  <table
  border="0"
  cellpadding="4"
  style="border-collapse:
         collapse">
    <tr>
      <td nowrap>
        <form
        name="frm"
        style="text-align:
               center;
               background-color:
               #E7E7DA">
          <b>
          &nbsp;&nbsp;
          Wyszukiwanie
          maksymalnego
          &nbsp;&nbsp;<br>
          prefikso-sufiksu
          <br/></b>
          (C)2026 mgr
          Jerzy Wałaszek
          <hr>
          <input
          type="button"
          value="Wykonaj"
          name="B1"
          onclick="main()">
          <hr>
          <b>Wynik:</b>
          <div id="out">.</div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script type=text/javascript
        language=javascript>

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

function main()
{
  var s, i, n;

  // generujemy łańcuch
  s = "";
  for(i = 0; i < 40; i++)
    s += String.fromCharCode(65 +
         Math.floor(
         Math.random() * 2));

  // szukamy prefikso-sufiksu
  n = s.length;
  for(i = n-1; i>0; i--)
    if(s.substr(0, i) ==
       s.substr(n - i, i)) break;
  s  = "<pre> " + s + " "
  s += "<br/> " + i + "</pre>";
  document.getElementById("out")
  .innerHTML = s;
}

</script>

  </body>
</html>

do podrozdziału do strony

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.

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

# 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()

do podrozdziału do strony

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.

Wyszukiwanie maksymalnego prefikso-sufiksu

Problem

Rozwiązanie nr 1

Algorytm naiwny wyszukiwania maksymalnego prefikso-sufiksu

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie nr 2

Własność 1 – rozszerzenie prefikso-sufiksu

Własność 2 – redukcja prefikso-sufiksu

Algorytm Morrisa-Pratta wyszukiwania maksymalnego prefikso-sufiksu

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy