Pagini recente » Cod sursa (job #1765602) | Cod sursa (job #390974) | Cod sursa (job #2593108) | Cod sursa (job #273134) | Cod sursa (job #1976253)
#include <cstdio>
#include <ctype.h>
char getch(FILE *fin) {
char ch = fgetc(fin);
while(ch == ' ')
ch = fgetc(fin);
return ch;
}
const int MAX_N = 2000000;
char word[1+MAX_N+1+MAX_N];
int v[1+MAX_N+1+MAX_N];
int top;
int r[1000];
inline void kmp(int n1, int n2) {
word[n1 + 1] = -1;
for(int i = 2; i <= n1 + n2 + 1; ++i) {
int j = i - 1;
while(j > 0 && word[i] != word[v[j] + 1])
j = v[j];
if(word[v[j] + 1] == word[i])
v[i] = v[j] + 1;
else
v[i] = 0;
if(v[i] == n1) {
if(top < 1000)
r[top] = i - 1 - 2 * n1;
top++;
}
}
}
int main() {
int n1, n2;
FILE *fin = fopen("strmatch.in", "r");
n1 = n2 = 0;
char ch = getch(fin);
while(isalpha(ch)) {
word[++n1] = ch;
ch = getch(fin);
}
ch = getch(fin);
while(isalpha(ch)) {
++n2;
word[n1 + 1 + n2] = ch;
ch = getch(fin);
}
fclose(fin);
kmp(n1, n2);
FILE *fout = fopen("strmatch.out", "w");
fprintf(fout, "%d\n", top);
for(int i = 0; i < top && i < 1000; ++i)
fprintf(fout, "%d ", r[i]);
fclose(fout);
return 0;
}