Mai intai trebuie sa te autentifici.
Cod sursa(job #793517)
| Utilizator | Data | 3 octombrie 2012 14:19:18 | |
|---|---|---|---|
| Problema | Potrivirea sirurilor | Scor | 60 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.89 kb |
#include <cstdio>
#include <cstring>
#define L 2000010
char T[L],P[L];
int pi[L],poz[L];
int nr=0, M,N;
void prefix() {
int k=0;
for (int i=2; i<N; ++i) {
while (k>1 && P[k+1]!=P[i])
k = pi[k];
if (P[k+1] == P[i]) ++k;
pi[i] = k;
}
}
void cauta () {
int k=0;
for (int i=1; i<M; ++i) {
while (k>0 && T[i]!=P[k+1])
k = pi[k];
if (T[i]==P[k+1]) ++k;
if (k==N-1) k=pi[k], poz[nr++] = i-N+1;
}
}
void afisare() {
printf("%d\n", nr);
if (nr>1000) nr = 1000;
for (int i=0; i<nr; ++i)
printf("%d ", poz[i]);
}
int main () {
freopen("strmatch.in","rt",stdin);
freopen("strmatch.out","wt",stdout);
fgets(P+1,L,stdin);
fgets(T+1,L,stdin);
M=strlen(T+1);
N=strlen(P+1);
prefix();
cauta();
afisare();
return 0;
}
