Pagini recente » Cod sursa (job #2966830) | Cod sursa (job #2540327) | Cod sursa (job #2966829) | Cod sursa (job #3339688) | Cod sursa (job #2540318)
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
const int lmax = 2000000;
const int nmax = 1000;
char A[lmax], B[lmax];
int lcp[lmax];
bool match[lmax];
void preProcessKMP(){
int i,j,n;
n = strlen(A);
j = 0, lcp[0] = 0;
for(i=1; i<n;){
if(A[i] == A[j]){
lcp[i] = j+1;
i++, j++;
}
else{
if(j != 0)
j = lcp[j-1];
else{
lcp[i] = 0;
i++;
}
}
}
}
int KMP(){
int sol = 0, j = 0;
int m = (int)strlen(B), n = (int)strlen(A);
for(int i=0; i<m;){
if(B[i] == A[j])
i++, j++;
else{
if(j != 0)
j = lcp[j-1];
else
i++;
}
if(j == n){
sol++;
match[i-n-1] = true;
j = lcp[j-1];
if(sol == nmax)
return sol;
}
}
return sol;
}
int main()
{
FILE *fin, *fout;
fin = fopen("strmatch.in","r");
fout = fopen("strmatch.out","w");
fscanf(fin,"%s\n%s\n",A,B);
preProcessKMP();
int sol = KMP();
fprintf(fout,"%d\n",sol);
for(int i=0; i<(int)strlen(B); i++)
if(match[i] == true)
fprintf(fout,"%d ",i+1);
fclose(fin);
fclose(fout);
return 0;
}