Algorytmy i Struktury Danych - Wyszukiwanie słów podwójnych

Pierwsze rozwiązanie polega na bezpośrednim sprawdzaniu każdego podsłowa łańcucha s, czy jest ono słowem podwójnym. Złożoność obliczeniowa takiego podejścia jest klasy O(n³). Słowo podwójne musi się składać z parzystej liczby znaków – inaczej nie da się go podzielić na dwa podsłowa. Sprawdzanie polega na porównywaniu ze sobą znaków pierwszej i drugiej połówki. Jeśli są zgodne, słowo jest podwójne.

Algorytm wyszukiwania słów podwójnych w łańcuchu – wersja nr 1

Wejście:

s : łańcuch tekstowy.

Wyjście:

Wszystkie słowa podwójne zawarte w łańcuchu s.

Elementy pomocnicze:

i, j : indeksy znaków w łańcuchu s; i, j ∈ N.
m : długość łańcucha s; m ∈ N.
n : długość podsłowa; n ∈ N.

Lista kroków:

K01: m ← |s|
K02: Dla i = 0, 1, …, n-2: ; przeglądamy łańcuch s
     wykonuj kroki K03…K07
K03:   n ← 2 ; rozpoczynamy od słowa o długości 2
K04:   Dopóki i = n ≤ m:
       wykonuj kroki K05…K07
K05:   j ← i+n div 2 ; j wskazuje pierwszy znak
       ; drugiej połówki słowa
K06:   Jeśli s[i:j] = s[j:i+n], ; sprawdzamy, 
       to pisz s[i:i+n] ; czy słowo jest podwójne
K07:   n ← n+2 ; przechodzimy do następnego słowa
K08: Zakończ

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 20 znakowy łańcuch zbudowany ze znaków {A, B}, wyszukuje w nim wszystkie słowa podwójne i wypisuje je z odpowiednim przesunięciem.

Pascal

// Wyszukiwanie słów podwójnych
// Data: 23.07.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

program prg;

const M = 20; // długość łańcucha s

var
  s : ansistring;
  i, j, n : integer;

begin

  // generujemy łańcuch s
  randomize;
  s := '';
  for i := 1 to M do
    s := s+chr(65+random(2));

  // wypisujemy łańcuch s
  writeln(s);

  // szukamy słów podwójnych
  for i := 1 to M-1 do
  begin
    n := 2;
    while i+n <= M+1 do
    begin
      j := i+n div 2;
      if copy(s, i, j-i) = copy(s, j, j-i) then
      begin
        for j := 2 to i do write(' ');
        writeln(copy(s, i, n));
      end;
      inc(n, 2);
    end;
  end;
  writeln;
end.

C++

// Wyszukiwanie słów podwójnych
// Data: 23.07.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
  const int M = 20; // długość łańcucha s
  string s;
  int i, j, n;

  // generujemy łańcuch s
  srand(time(NULL));
  s = "";
  for(i = 0; i < M; i++)
    s += char(65+rand()%2);

  // wypisujemy łańcuch s
  cout << s << endl;

  // szukamy słów podwójnych
  for(i = 0; i < M-1; i++)
    for(n = 2; i+n <= M; n += 2)
    {
      j = i+n/2;
      if(s.substr(i, j-i) == s.substr(j, j-i))
      {
        for(j = 0; j < i; j++)
          cout << " ";
        cout << s.substr(i, n) << endl;
      }
    }
  cout << endl;
  return 0;
}

Basic

' Wyszukiwanie słów podwójnych
' Data: 23.07.2008
' (C)2020 mgr Jerzy Wałaszek
'-----------------------------

Const M = 20 ' długość łańcucha s
Dim As String s
Dim As Integer i, j, n

' generujemy łańcuch s
Randomize
s = ""
For i = 1 To M
  s += Chr(65+Cint(Rnd))
Next

' wypisujemy łańcuch s
Print s

' szukamy słów podwójnych
For i = 1 To M-1
  n = 2
  While i+n <= M+1
    j = i+n\2
    If Mid(s, i, j-i) = Mid(s, j, j-i) Then
      For j = 2 To i
        Print " ";
      Next
      Print Mid(s, i, n)
    End If
    n += 2
  Wend
Next
Print
End

Python (dodatek)

# Wyszukiwanie słów podwójnych
# Data: 20.03.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random

M = 20 # długość łańcucha s

# generujemy łańcuch s
s = ""
for i in range(M):
    s += chr(random.randrange(65, 67))
# wypisujemy łańcuch s
print(s)
# szukamy słów podwójnych
for i in range(M-1):
    n = 2
    while(i+n <= M):
        j = i+n//2
        if s[i:j] == s[j:j+n//2]:
            for k in range(i):
                print(" ", end="")
            print(s[i:i+n])
        n += 2
print()

Wynik:

BABABBABBABBABBABAAB
BABA
 ABAB
  BABBAB
  BABBABBABBAB
   ABBABB
   ABBABBABBABB
    BB
    BBABBA
    BBABBABBABBA
     BABBAB
     BABBABBABBAB
      ABBABB
       BB
       BBABBA
        BABBAB
         ABBABB
          BB
          BBABBA
           BABBAB
             BB
              BABA
                 AA

do podrozdziału do strony

Pierwszy algorytm posiada sześcienną klasę złożoności obliczeniowej O(n³), gdzie n jest długością przeszukiwanego łańcucha s. W praktyce jednak działa on szybciej, ponieważ niezgodność fragmentów łańcucha zwykle wykrywana jest na początku po kilku testach. Zaletą jest prostota algorytmu.

Jeśli wykorzystamy w odpowiedni sposób algorytm Morrisa-Pratta, to możemy zredukować klasę złożoności obliczeniowej do kwadratowej O(n²). W algorytmie MP jest wyznaczana dla wzorca s tablica Π zawierająca maksymalne szerokości prefikso-sufiksów. Na przykład, jeśli weźmiemy prefiks s[0:i], to Π[i] zawiera szerokość prefikso-sufiksu tego prefiksu:

obrazek

Na początek rozważymy wykrywanie słów podwójnych leżących na początku łańcucha s, a później uogólnimy tę operację na dowolną pozycję wewnątrz łańcucha. Ponieważ tablica Π jest tworzona dynamicznie w algorytmie MP, możemy w trakcie tego procesu badać jej zawartość. Jeśli i jest długością prefiksu s, to Π[i] jest długością prefikso-sufiksu dla tego prefiksu (patrz, rysunek powyżej). Mogą wystąpić trzy możliwe sytuacje:

1. Długość prefikso-sufiksu jest mniejsza od długości połowy prefiksu, czyli Π[i] < ⁱ/₂:

obrazek

W tym przypadku nie można utworzyć słowa podwójnego o szerokości i.

2. Długość prefikso-sufiksu jest równa długości połowy prefiksu, czyli Π[i] = ⁱ/₂:

obrazek

Prefiks s[0:i] jest słowem podwójnym, ponieważ składa się z dwóch, dokładnie takich samych podłańcuchów – prefiksu i sufiksu tworzących prefikso-sufiks.

3. Długość prefikso-sufiksu jest większa od długości połowy prefiksu, czyli Π[i] > ⁱ/₂:

obrazek

Zastanówmy się, kiedy prefiks s[0:i] może być słowem podwójnym. W tym celu przyjrzyjmy się poniższemu rysunkowi poglądowemu:

obrazek

Symbolem A oznaczmy pokrywający się fragment prefikso-sufiksu. Ponieważ prefiks i sufiks są sobie równe w prefikso-sufiksie, fragment A występuje również na początku prefiksu oraz na końcu sufiksu. Aby mogło powstać słowo podwójne o długości i znaków, i musi być parzyste. Dalej wspólny fragment A sam musi być słowem podwójnym – w przeciwnym razie początki dwóch podsłów byłyby różne. Podzielmy zatem fragment A na dwa fragmenty oznaczone małą literką a. Z ostatniego przykładu widzimy wyraźnie, iż pozostały obszar B musi być podłańcuchem pustym – w przeciwnym razie nie otrzymamy równości podsłowa lewego i prawego:

aaBa ≠ aBaa, jeśli B ≠ Ø

Sytuacja taka wystąpi, gdy szerokość pokrywającego się fragmentu A będzie dokładnie równa ¹/₃ i, czyli: 3Π[i] = 2i

Ostatni przypadek wystąpi, gdy zachodzi nierówność: 3Π[i] > 2i. Pokażemy, iż w takim razie prefiks s[0:i] jest słowem podwójnym, jeśli pokrywający się fragment prefikso-sufiksu sam jest słowem podwójnym. Przyjrzyjmy się poniższemu rysunkowi poglądowemu:

obrazek

Na początku prefiksu pozostaje fragment B. Następnie mamy pokrywający się fragment A i na końcu sufiksu pozostaje fragment C o tej samej długości co fragment B. Pokrywający się fragment A musi być słowem podwójnym – dzielimy go zatem na dwie połówki oznaczone małymi literami a. Otrzymujemy dwa podsłowa Ba oraz aC. Aby prefiks s[0:n] był słowem podwójnym, musi zachodzić równość:

Ba = aC

Przyrównujemy do siebie prefiks i sufiks prefikso-sufiksu. Fragment B jest również prefiksem podsłowa a, natomiast fragment C jest również sufiksem podsłowa a. Z tego prostego spostrzeżenia bezpośrednio wynika poszukiwana równość Ba = aC.

Pozostaje jedynie problem sprawdzenia, czy fragment A jest słowem podwójnym. Zwróć jednakże uwagę, iż jest on zawsze krótszy od prefiksu s[0:i] oraz jest zawsze prefiksem podłańcucha s[0:i]. Zatem algorytm już wcześniej sprawdzał, czy ten prefiks był słowem podwójnym. Dlatego wystarczy zapamiętać ten fakt w osobnej tablicy (nie zwiększymy złożoności czasowej, jednakże zwiększymy złożoność pamięciową) – lub po prostu sprawdzić, czy A jest słowem podwójnym (zwiększa się złożoność czasowa). W dodatkowej tablicy zapamiętujemy jedynie fakt, czy podsłowo A jest podwójne, zatem może to być tablica logiczna. Co więcej nie ma sensu zapamiętywać informacji o słowach zbudowanych z nieparzystej liczby znaków. Pozwala to zmniejszyć o połowę wielkość tej tablicy.

Podsumowując stwierdzamy:

2Π[i] < i : s[0:i] nie jest słowem podwójnym
2Π[i] = i : s[0:i] jest słowem podwójnym
3Π[i] < 2i : s[0:i] nie jest słowem podwójnym
3Π[i] ≥ 2i : s[0:i] jest słowem podwójnym, jeśli s[0:2Π[i]-i] (prefiks o długości równej pokrywającemu się fragmentowi prefikso-sufiksu) jest słowem podwójnym.

Wyszukanie wszystkich słów podwójnych w łańcuchu s sprowadza się do wyszukiwania tych słów w kolejnych sufiksach poczynając od niewłaściwego (obejmującego cały łańcuch) i kończąc na sufiksie dwuznakowym. Algorytm MP działa w czasie liniowym, natomiast operacja przeszukania wszystkich sufiksów łańcucha s będzie wymagała kwadratowej złożoności obliczeniowej. Złożoność pamięciowa algorytmu jest liniowa.

Algorytm wyszukiwania słów podwójnych w łańcuchu – wersja nr 2

Wejście:

s : łańcuch tekstowy.

Wyjście:

Wszystkie słowa podwójne zawarte w łańcuchu s.

Elementy pomocnicze:

i, j, k : indeksy znaków w łańcuchu s; i, j, k ∈ N.
n : długość łańcucha s; n ∈ N.
b : szerokość prefikso-sufiksu; b ∈ C.
b₂ : podwojona szerokość prefikso-sufiksu; b₂ ∈ C.
Π : tablica maksymalnych prefikso-sufiksów wyznaczanych przez algorytm MP. Indeksy od 0 do n. Π ∈ C.
P : tablica logiczna. Indeksy od 0 do n. Element P[ⁱ/₂] jest równy true, jeśli s[0:i] jest słowem podwójnym

Lista kroków:

K01: n ← |s| ; wyznaczamy długość łańcucha s
K02: Dla j = 0, 1, …, n-1: ; przeglądamy sufiksy s[j:n]
     wykonuj kroki K03…K17
K03:   Π[0] ← -1 ; algorytmem MP wyznaczamy kolejne
K04:   b ← -1 ; maksymalne prefikso-sufiksy dla
K05:   Dla i = 1, 2, …, n-j: ; danego sufiksu s[j:n]
       wykonuj kroki K06…K17
K06:     Dopóki (b > -1) ∧ (s[j+b] ≠ s[j+i-1]):
         wykonuj b ← Π[b]
K07:     b ← b+1
K08:     Π[i] ← b
K09:     b₂ ← b shr 1 ; podwójna szerokość prefikso-sufiksu
K10:     Jeśli i nieparzyste,        ; słowo podwójne posiada
         to następny obieg pętli K05 ; parzystą liczbę liter
K11:     P[i shr 1] ← false ; inicjujemy element tablicy P
K12:     Jeśli b₂ < i, ; przypadek nr 1
         to następny obieg pętli K05
K13:     Jeśli b₂ = i, ; przypadek nr 2
         to idź do kroku K16
K14:     Jeśli b₂+b < i shl 1, ; przypadek nr 3 z B ≠ Ø
         to następny obieg pętli K05
K15:     Jeśli P[(b₂-i) shr 1] = false, ; przypadek nr 3
         to następny obieg pętli K05    ;-obszar wspólny nie
                                        ; jest słowem podwójnym
K16:     P[i shr 1] ← true; ; zapamiętujemy, iż s[j:j+i]
         ; jest słowem podwójnym
K17:     Pisz s[j:j+i] ; wyprowadzamy znalezione słowo podwójne
K18: Zakończ

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 20 znakowy łańcuch zbudowany ze znaków {A, B}, wyszukuje w nim wszystkie słowa podwójne i wypisuje je z odpowiednim przesunięciem.

Pascal

// Wyszukiwanie słów podwójnych
// Data: 9.08.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

program prg;

const N = 20; // długość łańcucha s

var
  s : ansistring;
  i, j, k, b, b2 : integer;
  PI : array [0..N] of integer;
  P  : array [0..N shr 1] of boolean;

begin

  // generujemy łańcuch s
  randomize;
  s := '';
  for i := 1 to N do
    s := s+chr(65+random(2));

  // wypisujemy łańcuch s
  writeln(s);

  // szukamy słów podwójnych
  for j := 1 to N-1 do
  begin
    PI[0] := -1; b := -1;
    for i := 1 to N-j+1 do
    begin
      while(b > -1) and (s[j+b] <> s[j+i-1]) do
        b := PI[b];
      inc(b); PI[i] := b; b2 := b shl 1;
      if i and 1 = 0 then
      begin
        P[i shr 1] := false;
        if(b2 < i) then continue;
        if(b2 > i) then
        begin
          if b2+b < (i shl 1) then continue;
          if not (P[(b2-i) shr 1]) then continue;
        end;
        P[i shr 1] := true;
        for k := 2 to j do write(' ');
        writeln(copy(s, j, i));
      end;
    end;
  end;
  writeln;
end.

C++

// Wyszukiwanie słów podwójnych
// Data: 9.08.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

const int N = 20; // długość łańcucha s

int main()
{
  string s;
  int i, j, k, b, b2, PI[N+1];
  bool P[(N >> 1)+1];

  // generujemy łańcuch s
  srand(time(NULL));
  s = "";
  for(i = 0; i < N; i++)
    s += char(65+rand() % 2);

  // wypisujemy łańcuch s
  cout << s << endl;

  // szukamy słów podwójnych
  for(j = 0; j < N-1; j++)
  {
    PI[0] = b = -1;
    for(i = 1; i <= N-j; i++)
    {
      while((b > -1) && (s[j+b] != s[j+i-1]))
        b = PI[b];
      PI[i] = ++b; b2 = b << 1;
      if(!(i & 1))
      {
        P[i >> 1] = false;
        if(b2 < i) continue;
        if(b2 > i)
        {
          if(b2+b < (i << 1)) continue;
          if(!P[(b2-i) >> 1]) continue;
        }
        P[i >> 1] = true;
        for(k = 0; k < j; k++)
          cout << " ";
        cout << s.substr(j, i) << endl;
      }
    }
  }
  cout << endl;
  return 0;
}

Basic

' Wyszukiwanie słów podwójnych
' Data: 9.08.2008
' (C)2020 mgr Jerzy Wałaszek
'-----------------------------

Const N = 20 ' długość łańcucha s

Dim As String s
Dim As Integer i, j, k, b, b2, PI(N)
Dim As Byte P(N Shr 1)

' generujemy łańcuch s
Randomize
s = ""
For i = 1 To N
  s += Chr(65+Cint(Rnd))
Next

' wypisujemy łańcuch s
Print s

' szukamy słów podwójnych
For j = 1 To N-1
  PI(0) = -1: b = -1
  For i = 1 To N-j+1
    While (b > -1) And _
          (Mid(s, j+b, 1) <> Mid(s, j+i-1, 1))
      b = PI(b)
    Wend
    b += 1: PI(i) = b: b2 = b Shl 1
    if(i And 1) = 0 Then
      P(i Shr 1) = 0
      if(b2 < i) Then Continue For
      if(b2 > i) Then
        If b2+b < (i Shl 1) Then Continue For
        If P((b2-i) Shr 1) = 0 Then _
          Continue For
      End If
      P(i Shr 1) = 1
      For k = 2 To j
        Print " ";
      Next
      Print Mid(s, j, i)
    End If
  Next
Next
Print
End

Python (dodatek)

# Wyszukiwanie słów podwójnych
# Data: 21.03.2024
# (C)2024 mgr Jerzy Wałaszek
#-----------------------------

import random

N = 20 # długość łańcucha s

# tworzymy tablice
t_pi = [0] * (N+1)
t_p = [False] * ((N >> 1)+16)
# generujemy łańcuch s
s = ""
for i in range(N):
    s += chr(random.randrange(65, 67))
# wypisujemy łańcuch s
print(s)
# szukamy słów podwójnych
for j in range(N-1):
    t_pi[0] = -1
    b = -1
    for i in range(1, N-j+1):
        while (b > -1) and \
              (s[j+b] != s[j+i-1]):
            b = t_pi[b]
        b += 1
        t_pi[i] = b
        b2 = b << 1
        if not (i & 1):
            t_p[i >> 1] = False
            if b2 < i: continue
            if b2 > i:
                if b2+b < i << 1:
                    continue
                if not t_p[(b2-i) >> 1]:
                    continue
            t_p[i >> 1] = True
            for k in range(j):
                print(" ", end="")
            print(s[j:j+i])
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 słów podwójnych

Problem

Rozwiązanie nr 1

Algorytm wyszukiwania słów podwójnych w łańcuchu – wersja nr 1

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie nr 2

Algorytm wyszukiwania słów podwójnych w łańcuchu – wersja nr 2

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy