Pagini recente » Cod sursa (job #2694953) | Cod sursa (job #1808261) | Cod sursa (job #911098) | Cod sursa (job #2475879) | Cod sursa (job #1978843)
#include <cstdio>
const int MAX_N = 1000000;
char sir[MAX_N+1+MAX_N];
int d[MAX_N+1+MAX_N];
char getch(FILE *fin) {
char ch = fgetc(fin);
while(ch == ' ')
ch = fgetc(fin);
return ch;
}
int rez[1000];
int main() {
int n1, n2, st, dr, top = 0;
char ch;
n1 = n2 = 0;
FILE *fin = fopen("strmatch.in", "r");
ch = getch(fin);
while(ch != '\n') {
sir[n1++] = ch;
ch = getch(fin);
}
ch = getch(fin);
while(ch != EOF) {
sir[n1+(++n2)] = ch;
ch = getch(fin);
}
fclose(fin);
d[0] = 1;
st = dr = 0;
for(int i = 1; i < n1 + 1 + n2; ++i) {
if(i > dr) {
d[i] = 0;
while(sir[d[i]] == sir[i+d[i]])
++d[i];
st = i;
}
if(i < dr) {
d[i] = d[i - st];
if(i + d[i] >= dr) {
d[i] = dr - i + 1;
st = i;
while(sir[d[i]] == sir[i+d[i]])
++d[i];
dr = st + d[i] - 1;
}
}
if(d[i] == n1) {
if(top < 1000)
rez[top] = i - n1 - 1;
++top;
}
}
FILE *fout = fopen("strmatch.out", "w");
fprintf(fout, "%d\n", top);
for(int i = 0; i < top && i < 1000; ++i)
fprintf(fout, "%d ", rez[i]);
fclose(fout);
return 0;
}