https://pl.spoj.com/problems/AL_09_08
Skrócony opis problemu:
Dla danego tekstu $s$ o długości $n$ i wzorca $p$ o długości $m$ ($m \le n$) należy znaleźć ilość wystąpień $p$ w $s$. Zarówno $s$ jak i $p$ składają się z małych liter alfabetu łacińskiego, lecz w $p$ może pojawić się jeden znak '?', który będzie oznaczał dowolny znak.
Rozwiązanie naiwne:
Dla każdego spójnego podciągu $s$ o długości $m$ sprawdzamy czy jest równy $p$ i jeśli jest dodajemy do wyniku.
Złożoność: $O(n \cdot m)$, bo będzie $n-m+1$ takich podciągów o długości $m$, i dla każdego porównamy pesymistycznie cały ciąg $p$ o długości $m$.
Rozwiązanie sprytne:
TODO - hasze
Rozwiązanie jeszcze sprytniejsze:
Algorytm ten podpowiedział mi Damian Straszak.
Możemy skorzystać z algorytmu Knutha-Morrisa-Pratta (KMP), który pozwala na znalezienie wszystkich wzorców w tekście w czasie $O(n)$. My jednak mamy trochę utrudnione zadanie przez znak '?', który dopasowuje się do każdego znaku.
Możemy to rozwiązać zliczając ilość dopasowań wzorca dla każdej litery zamiast '?'. Czyli podstawiamy za '?' (jeśli jest we wzorcu) 'a' i zliczamy ilość dopasować, potem podstawiamy 'b' i dodajemy ilość nowych dopasowań do wyniku, itd.
Optymalizacja: Możemy sprawdzić, które litery występują w $s$ i tylko dla nich odpalać algorytm KMP. Złożoność pesymistyczna będzie taka sama, ale oszczędzi nam to obliczania wielu niepotrzebnych wyników pośrednich, które i tak będą równe 0.
Złożoność: $O(\sigma \cdot n)$, gdzie $\sigma$ to długość alfabetu (w naszym przypadku $\sigma = 26$). Dla każdej z $\sigma$ liter wykonujemy algorytm o złożoności $O(n)$. Zwróćmy też uwagę, że ten algorytm nie zależy od długości wzorca.
Algorytm: (jako funkcji KMP użyłem kodu z tej strony)
char str[200009], pattern[100009];
int n, m;
int KMP()
{
int KMPNext[m+1], b, i, pp, x = 0;
for(KMPNext[0] = b = -1, i = 1; i <= m; ++i)
{
while(b > -1 && pattern[b] != pattern[i-1])
b = KMPNext[b];
++b;
if(i == m || pattern[i] != pattern[b])
KMPNext[i] = b;
else
KMPNext[i] = KMPNext[b];
}
for(pp = b = i = 0; i < n; ++i)
{
while(b > -1 && pattern[b] != str[i])
b = KMPNext[b];
if(++b == m)
{
while(pp < i - b + 1)
++pp;
++pp; ++x;
b = KMPNext[b];
}
}
return x;
}
int main()
{
int i, j, x;
gets(str); gets(pattern);
n = strlen(str);
for(j = -1, m = 0; pattern[m]; ++m)
if(pattern[m] == '?')
j = m;
if(j < 0)
printf("%d\n", KMP());
else
{
for(x = i = 0; i < 27; ++i)
pattern[j] = i+'a',
x += KMP();
printf("%d\n", x);
}
}
Rozwiązanie najsprytniejsze:
Autorem algorytmu jest Maciek Boniecki.
Możemy rozpatrzeć wzorzec jako $p=a?b$. Dla obu części wywołujemy KMP i otrzymujemy 2 listy pozycji, na których mamy dopasowanie danej części do tekstu. Mając je, zliczamy ile jest takich par pozycji z pierwszej listy i pozycji z drugiej listy, że odległość między nimi wynosi długości pierwszej części $l$ powiększonej o 1 (czyli np. dla algoliga?pl odległość między parą pozycji powinna wynosić 9).Możemy to zrobić liniowo. Idziemy przez wszystkie elementy pierwszej listy i jednocześnie ustawiamy się również na początku drugiej listy. Jeśli odległość między elementami (indeksami) jest większa od $l$ to nie sprawdzamy kolejnych elementów drugiej listy (czyli de facto wychodzimy z zagnieżdżonej pętli). Jeśli jest mniejsza to idziemy do następnego elementu drugiej listy. Jeśli natomiast jest równa to inkrementujemy wynik i przechodzimy do następnego elementu listy albo zakańczamy przeszukiwanie dla danego elementu pierwszej listy. Nie ma to znaczenia, gdyż zaraz i tak wyjdziemy z zagnieżdżonej pętli i różnica będzie tylko od którego miejsca zaczniemy przebieg dla następnego elementu. Złożoność tej części jest liniowa, gdyż nie zaczynamy przechodzenie drugiej listy od początku za każdym razem, a przechodzimy każdy element drugiej listy raz.
Złożoność: $O(n)$, gdyż wykonujemy maksymalnie 2 wywołania funkcji KMP, a ewentualne połączenie dwóch wzorców również działa w czasie liniowym.
Ostateczny algorytm:
int tab[2][100009], len[2];
int KMP(char *str, int n, char *pattern, int m, int q)
{
int KMPNext[m+1], b, i, pp, x = 0;
for(KMPNext[0] = b = -1, i = 1; i <= m; ++i)
{
while(b > -1 && pattern[b] != pattern[i-1])
b = KMPNext[b];
++b;
if(i == m || pattern[i] != pattern[b])
KMPNext[i] = b;
else
KMPNext[i] = KMPNext[b];
}
for(pp = b = i = 0; i < n; ++i)
{
while(b > -1 && pattern[b] != str[i])
b = KMPNext[b];
if(++b == m)
{
while(pp < i - b + 1)
++pp;
++x;
tab[q][len[q]++] = pp++;
b = KMPNext[b];
}
}
return x;
}
char s[200009], p[100009];
int main()
{
int i, j, k, x, n, m;
get(s, p);
n = strlen(s);
for(j = -1, m = 0; p[m]; ++m) // znajdź '?' jeśli jest i oblicz długość wzorca
if(p[m] == '?')
j = m;
if(!j && m == 1) // jeśli wzorzec to "?"
printf("%d\n", n);
else if(j < 0) // jeśli nie ma '?'
printf("%d\n", KMP(s, n, p, m, 0));
else if(!j) // jeśli '?' jest na początku
printf("%d\n", KMP(s+1, n-1, p+1, m-1, 0));
else if(j == m-1) // jeśli '?' jest na końcu
printf("%d\n", KMP(s, n-1, p, m-1, 0));
else // jeśli '?' jest w środku
{
x = len[0] = len[1] = 0;
KMP(s, n, p, j, 0); // dopasuj pierwszą część wzorca
KMP(s, n, p+j+1, m-j-1, 1); // i drugą
for(i = k = 0; i < len[0]; ++i) // dla każdego wystąpienia pierwszej części wzorca
for(; k < len[1]; ++k) // sprawdź czy jest wystąpienie drugiej części - takie, żeby długość się zgadzała
if(tab[1][k] == tab[0][i]+j+1) // jeśli jest to inkrementuj wynik; tutaj możemy równie dobrze dać breaka, ale jeśli nie damy to w następnym przebiegu i tak wejdziemy do poniższego elsa
++x;
else if(tab[1][k] > tab[0][i]+j+1) // jeśli w drugiej części wzorca danego dopasowania nie da się połączyć z dopasowaniem pierwszej części to przejdź dalej (i pomiń to dopasowanie drugiej części)
break;
printf("%d\n", x);
}
}
Brak komentarzy:
Prześlij komentarz