Pagini recente » Cod sursa (job #1622076) | Cod sursa (job #1468563) | Cod sursa (job #1468546) | Cod sursa (job #2966931) | Cod sursa (job #2540314)
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
const int lmax = 2000000;
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];
}
}
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;
}