Pagini recente » Cod sursa (job #830718) | Borderou de evaluare (job #1698045) | Cod sursa (job #2327314) | Cod sursa (job #1415548) | Cod sursa (job #793517)
Cod sursa(job #793517)
#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;
}