Pagini recente » Cod sursa (job #571791) | Cod sursa (job #123051) | Cod sursa (job #344917) | Cod sursa (job #574745) | Cod sursa (job #1376548)
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define MAXL 2000005
FILE *fin = fopen("strmatch.in", "r");
FILE *fout = fopen("strmatch.out", "w");
char A[MAXL+1], B[MAXL+1];
int PI[MAXL+1];
int n, m;
int pos[1001];
inline void constr_prefix(){
// table:
/*
* char: |a|b|a
* index:|0|1|2
* value:|0|0|1
* for "abab" -> prefixes = {"aba", "ab", a"}
* -> suffixes = {"bab", "ab", b"}
*/
PI[1] = 0;
int k = 0;
for(int i = 1; i < n; i++) {
while((k>0) && (A[k] != A[i])) k = PI[k-1];
if(A[k] == A[i]) k++;
PI[i] = k;
}
}
int main()
{
int rd = fscanf(fin, "%s\n%s", A,B);
n = strlen(A);
m = strlen(B);
constr_prefix();
int matched = 0;
int k = 0;
for(int i = 0; i < m; i++) {
while((k > 0) && (A[k] != B[i])) k = PI[k-1];
if(A[k] == B[i]) k++;
if(k==n) {
matched++;
if(matched<= 1000) pos[matched-1] = i-n+1;
}
}
fprintf(fout, "%d\n", matched);
int N = (matched > 1000)?1000:matched;
for(int i = 0; i < N; i++)
fprintf(fout, "%d ", pos[i]);
fprintf(fout, "\n");
fclose(fout);
}