Pagini recente » Monitorul de evaluare | Cod sursa (job #2173480) | Cod sursa (job #1031881) | Cod sursa (job #2104255) | Cod sursa (job #3141550)
/**
Avem un text B cu lungimea m. m<=100000
Avem si un cuvant A de lungime n. n<=100000
Cuvantul poate fi oricat de lung.
Toate aparitiile cuvantului ca secventa in text.
**/
#include <fstream>
#include <cstring>
using namespace std;
char a[2000002], b[2000002];
int sol[1001], p[2000001];
int n, m, L, k, i;
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
int main () {
fin>>a+1>>b+1;
n = strlen(a+1); /// ma intereseaza din a caractere pe pozitii de la 1 la n
m = strlen(b+1); /// ma intereseaza din b caractere pe pozitii de la 1 la m
/// KMP obtine timp de calcul liniar (n+m)
/**
Pasul 1.
Facem o preprocesare pe cuvantul a.
Vom construi, pentru fiecare pozitie i din a (de la 1 la n)
o valoare p[i] = lungimea maxima a unui sufix terminat la pozitia i
care este totodata si prefix (si sa nu fie chiar identic cu toata secventa)
numele p vine de la prefix
sirul a
i
abaxababcxyab
0010123200012
**/
p[1] = 0;
L = 0;
for (i=2;i<=n;i++) {
/// calculez pe p[i] (ma voi folosi de faptul ca am p calculat pentru pozitiile anterioare)
/// in cadrul algoritmului, valoarea ultimului p calculat, adica
/// p[i-1] o tin intr-o variabila L (care va fi updatata si atribuita lui p[i])
while (L != 0 && a[i] != a[L+1])
L = p[L];
/// am tot scurtat sufixele de la pozitia i care sunt si prefixe
/// pana cand fie am ajuns la 0 fie am gasit ca pe unul dintre ele il
/// pot extind
if (a[i] == a[L+1]) /// in particular asta poate fi si cand L=0
L++;
p[i] = L;
}
/// codul de mai sus este liniar.
/// while consuma strict din cresterile lui L
/// dar L este incrementat cu 1 intr-un if din for
/// deci numarul total de pasi ai lui while nu poate fi mai mai mare ca L-1
/**
pe sirul aaaaaaa, p ar fi fost
p 0123456
**/
/**
Pasul 2
in situl b (textul) la o anumita pozitie i, vom calcula L ca fiind
lungimea maxima a unui sufix din b (terminat la pozitia i)
care este totodata prefix in a.
Automat, daca gasesc un astfel de sufix in b care este prefix de lungime
chiar n in a, inseamna ca am o potrivire.
**/
L = 0;
for (i=1;i<=m;i++) {
while (L!=0 && b[i] != a[L+1])
L = p[L];
/**
L este valoarea calculata la pasul i-1
cautam ca elemenul curent din b sa extinda acest predix de lungime L
din a, iar daca nu se poate il scurtam pe acest prefix candidat ca la
codul anterior
**/
if (b[i] == a[L+1])
L++;
if (L == n) {
k++;
if (k <= 1000)
sol[k] = i-n+1; /// cu indexare de la 1
L = p[L]; /// nu mai putem extinde prefixul de lungime n
/// ci cel mai bun prefix al sau
}
}
fout<<k<<"\n";
if (k > 1000)
k = 1000;
for (i=1;i<=k;i++)
fout<<sol[i]-1<<" ";
}
/**
brut are complexitate
for (i=1;i<=m-n+1) {
/// verificam daca sirul a apare ca secventa in b incepand cu pozitia i
ok = 1;
for (j=1;j<=n;j++)
comparam(a[j] cu b[i+j-1]);
}
duce la n*m
**/