Pagini recente » Cod sursa (job #2049110) | Cod sursa (job #944261) | Cod sursa (job #1864643) | Cod sursa (job #2137424) | Cod sursa (job #154573)
Cod sursa(job #154573)
#include <cstdio>
#include <cstring>
#define MAXN 2000005
#define MAXP 1024
char Text[MAXN], Word[MAXN];
int Pi[MAXN], Match[MAXP];
void KMPFailureFunction() {
// Pi[i] = lungimea celui mai mare prefix care e si sufix
// al prefixului de lungime i din cuvant (0..i-1)
// abc***abc????????
// Pi[9] = 3
Pi[0] = -1;
Pi[1] = 0; // ne intereseaza doar prefixe proprii
int i, k, n = strlen(Word);
// i = lungimea pentru care calculez Pi[i]
// k = lungimea prefixului la sfarsitul caruia vreau sa adaug
// caracterul i - 1
// Calculez pentru lungimea i
// S = Word
// <---------------------i------------------------->
// -------------------------------------------------
// | +++++++ +++++++ +++++++ +++++++ |
// | +abc +Z???+ abc+Y ... +abc +????+ abc+ |X
// | +++++++ +++++++ +++++++ +++++++ |
// -------------------------------------------------
// X = S(i - 1) - al i-lea element
// Y = S(k) - indexare de la 0 (al k + 1-lea element)
// <--------k-------->
// <-Pi[k]->
// Initial incerc sa adaug X la prefixul maxim obtinut deja - lungimea lui e k
// Pentru asta trebuie ca urmatorul caracter dupa secventa de k caractere intiala sa corespunda cu X
// Celelalte k caractere de la inceput respectiv sfarsit corespund datorita
// definitiei lui k (lungime celui mai lung prefix care e si sufix)
// Daca cele 2 caractere corespund, Pi[i] = k + 1 (Y-ul se poate inlocui cu X pe desen)
// Daca cele 2 caractere nu corespund, inseamna ca cel mai lung prefix care e si sufix din primele i caractere
// e mai scurt. Pentru a nu face verificari inutile observam ca:
// Daca k e lungimea celui mai lung prefix care e si sufix din primele i - 1 caractere,
// PREFIXUL PRIMELOR I CARACTERE ESTE SI PREFIX AL PRIMELOR K CARACTERE
// SUFIXUL PRIMELOR I CARACTERE ESTE SI SUFIXUL ULTIMELOR K CARACTERE
// De aceea, este importanta lungimea celui mai lung prefix care e si sufix al primelor k caractere
// Valoarea este deja calculata - este Pi[k]
// Urmatoarea comparatie va fi deci intre Z si X, Z = S(Pi[k]) - indexare de la 0
// Daca Z != X, se repeta pasul cu Pi[Pi[k]] si tot asa pana cand, in cel mai rau caz nu corespund caractere deloc
// Asta se intampla cand k = 0. In Acest caz, Pi[i] = 0
// In momentul in care am aflat acel k pentru care caracterele sa se potriveasca, il vom creste cu 1
// pentru ca acum, lungimea celui mai bun prefix care e si sufix este k + 1 (desen)
for (i = 2, k = 0; i <= n; ++ i) {
while (k > 0 && Word[i - 1] != Word[k]) // tot merg pe prefixe incercand sa gasesc Y-ul care sa fie egal cu X-ul
k = Pi[k];
if (Word[i - 1] == Word[k]) // daca il gasesc, lungimea perfixului care este si sufix este cu 1 mai mare
++ k;
Pi[i] = k;
}
}
void KMPSearch() {
int i, k, n = strlen(Word), m = strlen(Text);
// exact ca la functia precedenta dar acum caracterul pe care vreau sa-l adaug
// face parte din Text
for (i = 1, k = 0; i <= m; ++ i) {
while (k > 0 && Word[k] != Text[i - 1])
k = Pi[k];
if (Word[k] == Text[i - 1])
++ k;
if (k == n) {
Match[++ Match[0]] = i - k;
if (Match[0] == 1000)
return;
}
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", Word, Text);
KMPFailureFunction();
KMPSearch();
printf("%d\n", Match[0]);
for (int i = 1; i <= Match[0]; ++ i)
printf("%d ", Match[i]);
return 0;
}