Pagini recente » Cod sursa (job #1765343) | Cod sursa (job #1249484) | Cod sursa (job #1058570) | Cod sursa (job #1123586) | Cod sursa (job #555912)
Cod sursa(job #555912)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 2000010
int N, M, sol;
int pi[maxn], potr[1024];
char P[maxn], T[maxn];
int main() {
FILE *f1=fopen("strmatch.in", "r"), *f2=fopen("strmatch.out", "w");
int i, k;
fscanf(f1, "%s\n", P + 1);
N = strlen(P + 1);
fscanf(f1, "%s\n", T + 1);
M = strlen(T + 1);
k = 0;
for(i=2; i<=N; i++) {
while(k > 0 && P[i] != P[k + 1]) {
k = pi[k];
}
if(P[i] == P[k + 1]) k ++;
pi[i] = k;
}
k = 0;
for(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) {
sol ++;
if(sol <= 1000) { potr[sol] = i - N; }
}
}
fprintf(f2, "%d\n", sol);
for(i=1; i<=min(sol, 1000); i++) {
fprintf(f2, "%d ", potr[i]);
} fprintf(f2, "\n");
fclose(f1); fclose(f2);
return 0;
}