Wyszukiwanie słów podwójnych


Tematy pokrewne   Podrozdziały
Łańcuchy znakowe
Podstawowe pojęcia dotyczące przetwarzania tekstów
Podstawowe operacje na łańcuchach znakowych
Naiwne wyszukiwanie wzorca w tekście
Wyszukiwanie maksymalnego prefikso-sufiksu
Szybkie wyszukiwanie wzorca algorytmem Morrisa-Pratta
Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta
Szybkie wyszukiwanie wzorca uproszczonym algorytmem Boyera-Moore'a
Szybkie wyszukiwanie wzorca pełnym algorytmem Boyera-Moore'a
Wyszukiwanie wzorca algorytmem Karpa-Rabina
Zliczanie słów w łańcuchu
Dzielenie łańcucha na słowa
Wyszukiwanie najdłuższego słowa w łańcuchu
Wyszukiwanie najdłuższego wspólnego podłańcucha
Wyszukiwanie najdłuższego wspólnego podciągu
Wyszukiwanie najkrótszego wspólnego nadłańcucha
Wyszukiwanie słów podwójnych
Wyszukiwanie palindromów
MasterMind – komputer kontra człowiek
MasterMind – człowiek kontra komputer
Szyfr Cezara
Szyfrowanie z pseudolosowym odstępem
Szyfry przestawieniowe
Szyfr Enigmy
Szyfrowanie RSA
Dodawanie dużych liczb
Mnożenie dużych liczb
Potęgowanie dużych liczb
Duże liczby Fibonacciego
Haszowanie
Podstawowe operacje na tablicach
  Rozwiązanie nr 1
Rozwiązanie nr 2

 

Problem

W łańcuchu s znaleźć wszystkie słowa podwójne.


Przez słowo podwójne (ang. square word) będziemy rozumieli łańcuch tekstowy, który możemy rozdzielić na dwa identyczne podłańcuchy.

 

Przykład:

ABBCABBC – jest słowem podwójnym zbudowanym z dwóch identycznych podsłów ABBC

ABBCABBD – nie jest słowem podwójnym

 

Rozwiązanie nr 1

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(n3). 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, wykonuj K03...K07 ; przeglądamy łańcuch s
K03:     n ← 2 ; rozpoczynamy od słowa o długości 2
K04:     Dopóki i + nm, wykonuj K05...K07  
K05:         ji + n div 2 ; j wskazuje pierwszy znak drugiej połówki słowa
K06:         Jeśli s[i:j] = s[j:i+n], to pisz s[i:i+n] ; sprawdzamy, czy słowo jest podwójne
K07:         nn + 2 ; przechodzimy do następnego słowa
K08: Zakończ  

 

Program

Ważne:

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.

 

Lazarus
// Wyszukiwanie słów podwójnych
// Data: 23.07.2008
// (C)2012 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.
Code::Blocks
// Wyszukiwanie słów podwójnych
// Data: 23.07.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <time.h>

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((unsigned)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;
}
Free Basic
' Wyszukiwanie słów podwójnych
' Data: 23.07.2008
' (C)2012 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
Wynik
ABBAABBAAABAABABBBAA
ABBAABBA
 BB
 BBAABBAA
   AA
     BB
       AA
        AA
        AABAAB
         ABAABA
           AA
            ABAB
               BB
                BB
                  AA

 

Wyszukiwanie słów podwójnych
(C)2012 mgr Jerzy Wałaszek


...

 

Rozwiązanie nr 2

Pierwszy algorytm posiada sześcienną klasę złożoności obliczeniowej O(n3), 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 O(n2). 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:

 

 

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] < i/2:

 

 

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] = i/2:

 

 

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] > i/2:

 

 

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:

 

 

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 1/3 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:

 

 

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. Wystarczy zatem 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:

  1. 2Π[i] < i    – s[0:i] nie jest słowem podwójnym
  2. 2Π[i] = i    – s[0:i] jest słowem podwójnym
  3. 3Π[i] < 2i  – s[0:i] nie jest słowem podwójnym
  4. 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
b2  – podwojona szerokość prefikso-sufiksu, b2 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[i/2] 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: wykonuj K03...K17 ; przeglądamy sufiksy s[j:n]
K03:     Π[0] ← -1 ; algorytmem MP wyznaczamy kolejne
K04:     b ← -1 ; maksymalne prefikso-sufiksy dla
K05:     Dla i = 1,2,...,n - j: wykonuj K06...KK17 ; danego sufiksu s[j:n]
K06:         Dopóki (b > -1) ∧ (s[j + b] ≠ s[j + i - 1]):
        wykonuj b ← Π[b]
 
K07:         bb + 1  
K08:         Π[i] ← b  
K09:         b2b shr 1 ; podwójna szerokość prefikso-sufiksu
K10:         Jeśli i nieparzyste, to następny obieg pętli K05 ; słowo podwójne posiada parzystą liczbę liter
K11:         P[i shr 1] ← false ; inicjujemy element tablicy P
K12:         Jeśli b2 < i, to następny obieg pętli K05 ; przypadek nr 1
K13:         Jeśli b2 = i, to idź do K16 ; przypadek nr 2
K14:         Jeśli b2 + b < i shl 1, to następny obieg pętli K05 ; przypadek nr 3 z B ≠ Ø
K15:         Jeśli P[(b2 - i) shr 1] = false, to następny obieg pętli K05 ; przypadek nr 3 - 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  

 

Program

Ważne:

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.

 

Lazarus
// Wyszukiwanie słów podwójnych
// Data: 9.08.2008
// (C)2012 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.
Code::Blocks
// Wyszukiwanie słów podwójnych
// Data: 9.08.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <time.h>

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];

// generujemy łańcuch s

  srand((unsigned)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;
}
Free Basic
' Wyszukiwanie słów podwójnych
' Data: 9.08.2008
' (C)2012 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

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.