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

©2022 mgr Jerzy Wałaszek
I LO w Tarnowie

Wyszukiwanie słów podwójnych

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Problem

W łańcuchu s  należy wyszukać 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 ( n 3 ). 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.

Zmienne 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 kroki K03...K07
przeglądamy łańcuch s
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  ],
        to pisz s [ i:i + n  ]
sprawdzamy, 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 <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;
}
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
Wynik:
ABBAABBAAABAABABBBAA
ABBAABBA
 BB
 BBAABBAA
   AA
     BB
       AA
        AA
        AABAAB
         ABAABA
           AA
            ABAB
               BB
                BB
                  AA
Wyszukiwanie słów podwójnych
(C)2020 mgr Jerzy Wałaszek


...

Na początek:  podrozdziału   strony 

Rozwiązanie nr 2

Pierwszy algorytm posiada sześcienną klasę złożoności obliczeniowej O ( n 3 ), 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 2 ). 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  ] < i/ 2:

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

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

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

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

Zmienne 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 2  – podwojona szerokość prefikso-sufiksu, b 2  ∈ 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 kroki 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 kroki K06...KK17
danego sufiksu s [ j:n ]
K06:         Dopóki ( b  > -1 ) ∧ ( s [ j + b  ] ≠ s [ j + i - 1 ] ):
        wykonuj b  ← Π [ b  ]
 
K07:         b  ← b  + 1  
K08:         Π [ i  ] ← b  
K09:         b 2b  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 b 2 < i,
        to następny obieg pętli K05
przypadek nr 1
K13:         Jeśli b 2 = i,
        to idź do kroku K16
przypadek nr 2
K14:         Jeśli b 2 = b  < i  shl 1,
        to następny obieg pętli K05
przypadek nr 3 z B ≠ Ø
K15:         Jeśli P [ ( b 2 - 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  

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 <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;
}
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
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
©2022 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.