Twoim zadaniem jest rozwiązanie problemu SLCSC, polegającego na znalezieniu najkrótszego możliwego kodu do rozwiązania problemu najdłuższej wspólnej kolejności .

Prawidłowe rozwiązanie problemu LCS przez dwa lub więcej ciągów S ₁ , S ... _n jest dowolny ciąg T maksymalnej długości tak, że znaki T pojawiają się we wszystkich S _I , w tej samej kolejności jak w T .

Zauważmy, że T nie musi być sub ciąg od S _í .

Przykład

Ciągi znaków axbyczi xaybzcmają 8 wspólnych podciągów o długości 3:

abc abz ayc ayz xbc xbz xyc xyz

Każde z nich stanowiłoby prawidłowe rozwiązanie problemu LCS.

Detale

Napisz program lub funkcję, która rozwiąże problem LCS, jak wyjaśniono powyżej, przestrzegając następujących zasad:

• Dane wejściowe będą składać się z dwóch lub więcej ciągów zawierających tylko małe litery.

  Możesz odczytać te ciągi jako tablicę ciągów lub pojedynczy ciąg z dowolnym ogranicznikiem.

• Twój kod musi wypisać dowolne z możliwych rozwiązań problemu, opcjonalnie poprzedzone wierszem wiersza lub otoczone cudzysłowami.

• Możesz założyć, że łańcuchy są krótsze niż 1000 znaków i że istnieje maksymalnie 20 łańcuchów.

  W tych granicach Twój kod powinien działać zgodnie z oczekiwaniami teoretycznymi (biorąc pod uwagę nieograniczony czas i pamięć).

• Twój kod musi wypełnić połączone przypadki testowe następnej sekcji w ciągu godziny na moim komputerze (Intel Core i7-3770, 16 GiB RAM).

  Podejścia, które po prostu powtarzają wszystkie możliwe podsekwencje, nie będą zgodne z terminem.

• Używanie wbudowanych, które trywializują to zadanie, takich jak np. LongestCommonSequence, Jest niedozwolone.

Obowiązują standardowe zasady gry w golfa .

Przypadki testowe

a
ab

Wynik: a

aaaaxbbbb
bbbbxcccc
ccccxaaaa

Wynik: x

hxbecqibzpyqhosszypghkdddykjfjcajnwfmtfhqcpavqrtoipocijrmqpgzoufkjkyurczxuhkcpehbhpsuieqgjcepuhbpronmlrcgvipvibhuyqndbjbrrzpqbdegmqgjliclcgahxoouqxqpujsyfwbdthteidvigudsuoznykkzskspjufgkhaxorbrdvgodlb
qnnprxqpnafnhekcxljyysobbpyhynvolgtrntqtjpxpchqwgtkpxxvmwwcohxplsailheuzhkbtayvmxnttycdkbdvryjkfhshulptkuarqwuidrnjsydftsyhuueebnrjvkfvhqmyrclehcwethsqzcyfvyohzskvgttggndmdvdgollryqoswviqurrqhiqrqtyrl

Wyjście: hxbbpyhogntqppcqgkxchpsieuhbncvpuqndbjqmclchqyfttdvgoysuhrrllub jakikolwiek inny podsekwencja o tej samej długości

riikscwpvsbxrvkpymvbbpmwclizxlhihiubycxmxwviuajdzoonjpkgiuiulbjdpkztsqznhbjhymwzkutmkkkhirryabricvhb
jnrzutfnbqhbaueicsvltalvqoorafnadevojjcsnlftoskhntashydksoheydbeuwlswdzivxnvcrxbgxmquvdnfairsppodznm
kzimnldhqklxyezcuyjaiasaeslicegmnwfavllanoolkhvqkjdvxrsjapqqwnrplcwqginwinktxnkfcuuvoyntrqwwucarfvjg

Wyjście: icsvllvjnlktywuarlub jakikolwiek inny podsekwencja o tej samej długości

rblartqkfggrjpiipuzzypkycnyckkcqceeujiyy
yfpnedyjtiwrhyuktripdwyvgkblzodeufkelhub
ywcyboxwqkibwvredkrbdsyudkulpvmhixeqxynh
bnxwahbzhwjxkotnvbxrojkkldtsodtjmvdrmbgr

Wyjście: krkklub jakikolwiek inny podsekwencja o tej samej długości

bwfscmotshoczmduwaev
coywaaizdaxjovipsmeh
dobzcpoiedenzlfdjpiu
bbhfeqscvvbwkuoxdoge
drqrzwbcpcsvneodelja

Wyjście: codelub jakikolwiek inny podsekwencja o tej samej długości

nqrualgoedlf
jgqorzglfnpa
fgttvnogldfx
pgostsulyfug
sgnhoyjlnfvr
wdttgkolfkbt

Wyjście: golflub jakikolwiek inny podsekwencja o tej samej długości

epopyfuhgowedpiqpgfj
ddxyestqynpwmytxhozm
ptubgzyqqksieoovuezv
tovotqmnhgzttfpywjgr
aomvytkgaijlgqzkljls
vzvxpaixrnprxvenbbuo
syfuwxlpcyontqlmfvib
arxleuomstkjegpduwcx
xgqrxaopouvkvwgbzewn
yggunddigctgpnuztzai
izroomywwztdymqszsuo
kiawjnxjncdtufhkrjsp

Dane wyjściowe: pusty ciąg

CJam, 31

q~L{_:&\f{_2$f#:).>j+}{,}$W>s}j

Wypróbuj online

9 bajtów dzięki Dennisowi!

Wyjaśnienie:

Algorytm ten wypróbowuje każdy możliwy znak dla pierwszej pozycji podsekwencji, zastępuje każdy ciąg podłańcuchem po pierwszym wystąpieniu tego znaku, a następnie wywołuje się rekurencyjnie (z zapamiętywaniem).

q~          read and evaluate the input (taken as an array)
L{…}j       execute block with recursive memoization and no starting values
  _         duplicate the array of strings
  :&\       intersect the strings as character sets and move before the array
             these are all the possible characters for the sequence
  f{…}      for each character and the array
    _2$     duplicate the array and the character
    f#      find the character position in each string
    :)      increment the positions (to skip the character)
    .>      slice each string starting at the corresponding position
    j       call the j block recursively
    +       concatenate the starting character with the result
  {,}$      sort resulting strings (one for each character) by length
  W>        keep only the last element, if any
  s         convert (from 0/1-string array) to string

Python - 665 644

Poziomy wcięć:

1: space
2: tab
3: tab + space
4: 2 tabs
5: 2 tabs + space

Kod definiuje funkcję o, która przyjmuje listę ciągów znaków jako argumenty i zwraca jeden z LCS dla tych ciągów.

def o(t):
 t=[[y for y in x if y in reduce(lambda x,y:x.intersection(y),t,set(t[0]))]for x in t];l=map(len,t);C=[0]*reduce(lambda x,y:x*-~y,l,1);y=lambda z:[x-1for x in z];m=len(t);e=enumerate
 def g(h):
    r,x=0,1
    for k,j in e(h):r+=-~j*x;x*=-~l[k]
    return r
 def f(h):
    i=len(h)
    if i==m:
     b=g(h);c=t[0][h[0]]
     for k,j in e(h):
         if t[k][j]!=c:break
     else:C[b]=1+C[g(y(h))];return
     r=0
     for k,_ in e(h):a=h[:];a[k]-=1;r=max(r,C[g(a)])
     C[b]=r;return
    for j,_ in e(t[i]):f(h+[j])
 def p(h):
    if min(h)==-1:return''
    v=C[g(h)]
    for k,_ in e(h):
        a=h[:];a[k]-=1
        if v==C[g(a)]:return p(a)
    return p(y(h))+t[0][h[0]]
 f([]);return p(y(l))

Kod testowy:

tests = [
"""
a
ab
""",
"""
aaaaxbbbb
bbbbxcccc
ccccxaaaa
""",
"""
hxbecqibzpyqhosszypghkdddykjfjcajnwfmtfhqcpavqrtoipocijrmqpgzoufkjkyurczxuhkcpehbhpsuieqgjcepuhbpronmlrcgvipvibhuyqndbjbrrzpqbdegmqgjliclcgahxoouqxqpujsyfwbdthteidvigudsuoznykkzskspjufgkhaxorbrdvgodlb
qnnprxqpnafnhekcxljyysobbpyhynvolgtrntqtjpxpchqwgtkpxxvmwwcohxplsailheuzhkbtayvmxnttycdkbdvryjkfhshulptkuarqwuidrnjsydftsyhuueebnrjvkfvhqmyrclehcwethsqzcyfvyohzskvgttggndmdvdgollryqoswviqurrqhiqrqtyrl
""",
"""
riikscwpvsbxrvkpymvbbpmwclizxlhihiubycxmxwviuajdzoonjpkgiuiulbjdpkztsqznhbjhymwzkutmkkkhirryabricvhb
jnrzutfnbqhbaueicsvltalvqoorafnadevojjcsnlftoskhntashydksoheydbeuwlswdzivxnvcrxbgxmquvdnfairsppodznm
kzimnldhqklxyezcuyjaiasaeslicegmnwfavllanoolkhvqkjdvxrsjapqqwnrplcwqginwinktxnkfcuuvoyntrqwwucarfvjg
""",
"""
rblartqkfggrjpiipuzzypkycnyckkcqceeujiyy
yfpnedyjtiwrhyuktripdwyvgkblzodeufkelhub
ywcyboxwqkibwvredkrbdsyudkulpvmhixeqxynh
bnxwahbzhwjxkotnvbxrojkkldtsodtjmvdrmbgr
""",
"""
bwfscmotshoczmduwaev
coywaaizdaxjovipsmeh
dobzcpoiedenzlfdjpiu
bbhfeqscvvbwkuoxdoge
drqrzwbcpcsvneodelja
""",
"""
nqrualgoedlf
jgqorzglfnpa
fgttvnogldfx
pgostsulyfug
sgnhoyjlnfvr
wdttgkolfkbt
""",
"""
epopyfuhgowedpiqpgfj
ddxyestqynpwmytxhozm
ptubgzyqqksieoovuezv
tovotqmnhgzttfpywjgr
aomvytkgaijlgqzkljls
vzvxpaixrnprxvenbbuo
syfuwxlpcyontqlmfvib
arxleuomstkjegpduwcx
xgqrxaopouvkvwgbzewn
yggunddigctgpnuztzai
izroomywwztdymqszsuo
kiawjnxjncdtufhkrjsp
"""
]

for s in tests:
 print o(s.strip().split())

Czas potrzebny na uruchomienie testów na moim komputerze:

$ time python 52808-shortest-longest-common-subsequence-code-golfed.py
a
x
hecbpyhogntqtpcqgkxchpsieuhbncvhuqndbjqmclchqyfhtdvgoysuhrrl
icsvllvanlktywuar
krkk
code
golf

        9.03 real         8.99 user         0.03 sys

Pyth, 59 58 55 35 bajtów

L&@Fb?+yPMbeeb@FeMbeolNmyXJbdP@bdlb

Wytnij aż 20 bajtów dzięki @isaacg!

Wersja 55-bajtowa:

DCHR?k!&.AH@FH?+Cm<1dHeeHql{medH1h.MlZ.eC++<Hk]<1b>HhkH

Odetnij 3 bajty, zmieniając .U@bZna @F(operator składania).

Wersja 58-bajtowa:

DCHR?k!&.AH.U@bZH?+Cm<1dHeeHql{medH1h.MlZ.eC++<Hk]<1b>HhkH

Odetnij bajt, zmieniając format warunku logicznego.

Wersja 59-bajtowa:

DCHR?k|!.AH!.U@bZH?+Cm<1dHeeHql{medH1h.MlZ.eC++<Hk]<1b>HhkH

To było trudne! Python ciągle się segreguje! Byłem całkiem pewien, że to jakiś błąd, ale nie udało mi się uzyskać minimalnego przypadku testowego. No cóż.

Ten algorytm oparłem na tym . Co jest w porządku, z tym wyjątkiem, że ten jest przeznaczony tylko dla dwóch łańcuchów. Musiałem go trochę ulepszyć, żeby działał dalej. Potem ostatni przypadek testowy trwał zbyt długo, więc musiałem dodać dodatkową kontrolę, aby wyjść z rekurencji, jeśli nie ma więcej typowych znaków.

Jest to dość powolne, ale powinno zająć mniej niż godzinę (miejmy nadzieję). Testuję na moim Core i3 z 6 GB pamięci RAM, więc Twój 16-GB Core i7 powinien przez to przejść. :)

Skorzystałem również z funkcji automatycznego zapamiętywania Pytha, aby trochę przyspieszyć.

EDYCJA : @Dennis powiedział, że mija!

Aby to przetestować, dodaj następujący wiersz:

CQ

i podaj mu listę ciągów poprzez standardowe wejście (np ['a', 'ab'].).

Objaśnienie dla wersji 35-bajtowej:

WIP

Objaśnienie dotyczące wersji 55-bajtowej:

DCH                                                        define a function C that takes a list of strings H
   R                                                       return the following expression
    ?                                                      if
      !&.AH@FH                                             there are no more common letters OR all the strings are empty
     k                                                     return the empty string
              ?          ql{medH1                          else if the last character of every string is equal
               +Cm<1dHeeH                                  return the result of adding the last character to recursion with every item without its last character
                                 h.MlZ.eC++<Hk]<1b>HhkH    otherwise, return the largest result of recursing len(H) times, each time with one element's last character cut off

C, 618 564 bajtów

d,M,N,A[9999][2];char*(R[9999][20]),b[1000];L(char**s,n){char*j[20],c,a=0;int x[n],y=n-1,z,i,t,m=0,w=1;for(;y;)x[y--]=999;for(;y<N;y++){for(i=0;i<n&&s[i]==R[y][i];i++);if(i/n){a=A[y][0];m=A[y][1];w=0;if(m+d<M||!a)goto J;else{c=a;goto K;}}}for(c=97;w&&c<'{';c++){K:t=1,y=1,z=1;for(i=0;i<n;j[i++]++){for(j[i]=s[i];*j[i]-c;j[i]++)t&=!!*j[i];y&=j[i]-s[i]>x[i]?z=0,1:0;}t&=!y;I:if(t){if(z)for(i=0;i<n;i++)x[i]=j[i]-s[i];d++,t+=L(j,n),d--,m=t>m?a=c,t:m;}}if(w){for(y=0;y<n;y++)R[N][y]=s[y];A[N][0]=a;A[N++][1]=m;}J:if(d+m>=M)M=d+m,b[d]=a;if(!d)N=0,M=0,puts(b);return m;}

I tutaj jest wyjaśnione, dla „czytelności”:

d,M,N,A[9999][2];
char*(R[9999][20]),b[1000];
L(char**s,n){
    char*j[20],c,a=0;
    int x[n],y=n-1,z,i,t,m=0,w=1;
    for(;y;)
        x[y--]=999;
    for(;y<N;y++){
        for(i=0;i<n&&s[i]==R[y][i];i++);
        if(i/n){
            a=A[y][0];
            m=A[y][1];
            w=0;
            if(m+d<M||!a)
                goto J;
            else{
                c=a;
                goto K;
            }
        }
    }
    for(c=97;w&&c<'{';c++){
        K:
        t=1,
        y=1,
        z=1;
        for(i=0;i<n;j[i++]++){
            for(j[i]=s[i];*j[i]-c;j[i]++)
                t&=!!*j[i];
            y&=j[i]-s[i]>x[i]?z=0,1:0;
        }
        t&=!y;
        I:
        if(t){
            if(z)
                for(i=0;i<n;i++)
                    x[i]=j[i]-s[i];
            d++,
            t+=L(j,n),
            d--,
            m=t>m?a=c,t:m;
        }
    }
    if(w){
        for(y=0;y<n;y++)R[N][y]=s[y];
        A[N][0]=a;
        A[N++][1]=m;
    }
    J:
    if(d+m>=M)
        M=d+m,b[d]=a;
    if(!d)
        N=0,M=0,puts(b);
    return m;
}

Panie i panowie! Popełniłem straszny błąd. Jest używany do być ładniejsza ... I goto mniej ... Przynajmniej teraz jest szybka .

Definiujemy funkcję rekurencyjną, Lktóra przyjmuje jako dane wejściowe tablicę stablic znaków i liczbę nłańcuchów. Funkcja wyświetla wynikowy ciąg znaków na standardowe wyjście i przypadkowo zwraca rozmiar znaków tego ciągu.

Podejście

Chociaż kod jest zawiły, strategia tutaj nie jest zbyt skomplikowana. Zaczynamy od dość naiwnego algorytmu rekurencyjnego, który opiszę za pomocą pseudokodu:

Function L (array of strings s, number of strings n), returns length:

Create array of strings j of size n;

For each character c in "a-z",
    For each integer i less than n,
         Set the i'th string of j to the i'th string of s, starting at the first appearance of c in s[i]. (e.g. j[i][0] == c)
         If c does not occur in the i'th string of s, continue on to the next c.
    end For

    new_length := L( j, n ) + 1; // (C) t = new_length
    if new_length > best_length
        best_character := c; // (C) a = best_character
        best_length := new_length; // (C) m = best_length
    end if
end For

// (C) d = current_depth_in_recursion_tree
if best_length + current_depth_in_recursion_tree >= best_found
     prepend best_character to output_string // (C) b = output_string
     // (C) M = best_found, which represents the longest common substring found at any given point in the execution.
     best_found = best_length + current_depth;
end if

if current_depth_in_recursion_tree == 0
    reset all variables, print output_string
end if 

return best_length

Ten algorytm sam w sobie jest dość okropny (znalazłem, że można go zmieścić w około ~ 230 bajtach). Nie w ten sposób uzyskuje się szybkie wyniki. Ten algorytm skaluje się niezwykle słabo przy długości łańcucha. Algorytm ten jest jednak dość dobrze skalować z większej liczby łańcuchów. Ostatni przypadek testowy zostałby rozwiązany praktycznie natychmiast, ponieważ żadne ciągi znaków nie smają cwspólnych znaków . Zaimplementowałem dwie główne sztuczki, które spowodowały niesamowity wzrost prędkości:

• Przy każdym wezwaniu do Lsprawdź, czy otrzymaliśmy już tę samą informację. Ponieważ w praktyce informacja jest przekazywana dookoła poprzez wskaźniki do tego samego zestawu strun, nie faktycznie trzeba porównać ciągi, tylko miejsca, które jest świetne. Jeśli okaże się, że już otrzymaliśmy te informacje, nie trzeba przeprowadzać obliczeń (przez większość czasu, ale uzyskanie danych wyjściowych sprawia, że ​​jest to trochę bardziej skomplikowane) i możemy uciec od samego powrotu długości. Jeśli nie znajdziemy dopasowania, zapisz ten zestaw danych wejściowych / wyjściowych, aby porównać z przyszłymi połączeniami. W kodzie C druga forpętla próbuje znaleźć dopasowania do danych wejściowych. Znane wskaźniki wejściowe są zapisywane R, a odpowiadające im wartości długości i znaków są przechowywane wA. Ten plan miał drastyczny wpływ na środowisko wykonawcze, szczególnie w przypadku dłuższych łańcuchów.

• Za każdym razem znaleźć lokalizacje cw s, istnieje szansa, wiemy, tuż nietoperza, że to, co odkryliśmy, nie jest optymalna. Jeśli każda lokalizacja cpojawi się po znanej lokalizacji innej litery, automatycznie wiemy, że cnie prowadzi to do optymalnego podciągu, ponieważ można w niej zmieścić jeszcze jedną literę. Oznacza to, że za niewielką opłatą możemy potencjalnie usunąć kilkaset wezwań do Ldużych ciągów. W powyższym kodzie C yjest zestaw flag, jeśli automatycznie wiemy, że ten znak prowadzi do nieoptymalnego ciągu, i zjest zestawem flag, jeśli znajdziemy znak, który ma wyłącznie wcześniejszy wygląd niż jakikolwiek inny znany znak. Obecne najwcześniejsze pojawienia się znaków są przechowywane wx. Obecna implementacja tego pomysłu jest nieco niechlujna, ale w wielu przypadkach niemal podwojona wydajność.

Dzięki tym dwóm pomysłom, co nie zakończyło się w ciągu godziny, zajęło teraz około 0,015 sekundy.

Prawdopodobnie istnieje wiele innych małych sztuczek, które mogą przyspieszyć wydajność, ale w tym momencie zacząłem martwić się o moją umiejętność gry w golfa. Wciąż nie jestem zadowolony z golfa, więc prawdopodobnie wrócę do tego później!

Czasy

Oto kod testowy, który zapraszam do wypróbowania online :

#include "stdio.h"
#include "time.h"

#define SIZE_ARRAY(x) (sizeof(x) / sizeof(*x))

int main(int argc, char** argv) {
    /* Our test case */
    char* test7[] = {
        "nqrualgoedlf",
        "jgqorzglfnpa",
        "fgttvnogldfx",
        "pgostsulyfug",
        "sgnhoyjlnfvr",
        "wdttgkolfkbt"
    };

    printf("Test 7:\n\t");
    clock_t start = clock();

    /* The call to L */
    int size = L(test7, SIZE_ARRAY(test7));


    double dt = ((double)(clock() - start)) / CLOCKS_PER_SEC;
    printf("\tSize: %d\n", size);
    printf("\tElapsed time: %lf s\n", dt);

    return 0;
}

Testy OP przeprowadziłem na laptopie wyposażonym w procesor Intel Core i7 1,7 GHz z ustawieniem optymalizacji na -Ofast. Symulacja wykazała, że ​​wymagany szczyt to 712 KB. Oto przykładowy przebieg każdego przypadku testowego z czasami:

Test 1:
    a
    Size: 1
    Elapsed time: 0.000020 s
Test 2:
    x
    Size: 1
    Elapsed time: 0.000017 s
Test 3:
    hecbpyhogntqppcqgkxchpsieuhbmcbhuqdjbrqmclchqyfhtdvdoysuhrrl
    Size: 60
    Elapsed time: 0.054547 s
Test 4:
    ihicvaoodsnktkrar
    Size: 17
    Elapsed time: 0.007459 s
Test 5:
    krkk
    Size: 4
    Elapsed time: 0.000051 s
Test 6:
    code
    Size: 4
    Elapsed time: 0.000045 s
Test 7:
    golf
    Size: 4
    Elapsed time: 0.000040 s
Test 8:

    Size: 0
    Elapsed time: 0.000029 s


Total time: 0.062293 s

Podczas gry w golfa dość znacząco poprawiłem wydajność, a ponieważ ludzie wydawali się lubić brutalną prędkość (0,013624 s, aby ukończyć wszystkie przypadki testowe łącznie) mojego poprzedniego 618-bajtowego rozwiązania, zostawię to tutaj w celach informacyjnych:

d,M,N,A[9999][2];char*(R[9999][20]),b[1000];L(char**s,n){char*j[20],c,a=0;int x[n],y,z,i,t,m=0,w=1;for(y=0;y<n;y++)x[y]=999;for(y=0;y<N;y++){for(i=0;i<n;i++)if(s[i]!=R[y][i])break;if(i==n){a=A[y][0];m=A[y][1];w=0;if(m+d<M||!a)goto J;else{c=a;goto K;}}}for(c=97;w&&c<'{';c++){K:t=1,y=1,z=1;for(i=0;i<n;j[i++]++){for(j[i]=s[i];*j[i]-c;j[i]++)if(!*j[i]){t=0;goto I;}if(j[i]-s[i]>x[i])z=0;if(j[i]-s[i]<x[i])y=0;}if(y){t=0;}I:if(t){if(z){for(i=0;i<n;i++){x[i]=j[i]-s[i];}}d++,t+=L(j,n),d--,m=t>m?(a=c),t:m;}}if(w){for(y=0;y<n;y++)R[N][y]=s[y];A[N][0]=a;A[N++][1]=m;}J:if(d+m>=M)M=d+m,b[d]=a;if(!d)N=0,M=0,puts(b);return m;}

Sam algorytm pozostaje niezmieniony, ale nowy kod opiera się na podziałach i trudniejszych operacjach bitowych, które ostatecznie spowalniają cały proces.

Python 2, 285

Kod:

import re
def f(s,a,b):
  if b==[]:return s+f('',[],a)
  if a==[]:return s+max([f(b[0][i],[b[0][i+1:]],b[1:]) for i in range(len(b[0]))],key=len) if b[0]!='' else ''
  return max([f(s,a+[b[0][i.start()+1:]],b[1:]) for i in re.finditer(s[-1],b[0])],key=len) if ~b[0].find(s[-1]) else ''

Stosowanie:

print f('',[],['axbycz','xaybzc'])

Wyjaśnienie:

To jest funkcja rekurencyjna. sto postać, której szukamy. azawiera listę ciągów pokrojonych po s. bzawiera listę ciągów jeszcze nietkniętych. fzwraca najdłuższy wspólny ciąg.

Pierwszy warunek sprawdza, czy skończyliśmy przechodzić przez wszystkie łańcuchy. jeśli tak, oznacza to, że sjest pospolitym charakterem i powraca w sposzukiwaniu bardziej powszechnych znaków.

Drugi warunek sprawdza, czy nie zaczynamy przechodzić przez dowolny ciąg znaków, co oznacza, że ​​nie mamy nawet znaku ( a==[]jest równoważny s==''). jeśli tak, sprawdzamy każdy znak pierwszego ciągu w b.

Ostatni wiersz przenosi pierwszy ciąg znaków bdo a, znajdując każde wystąpienie stego ciągu.

Przy pierwszym wywołaniu spowinien być pusty ciąg. apowinna być pusta lista i bpowinna zawierać wszystkie ciągi.