Pagini recente » Cod sursa (job #583851) | Cod sursa (job #921171) | Cod sursa (job #1126552) | Cod sursa (job #899310) | Cod sursa (job #1725483)
#include <fstream>
#include <string.h>
#define DIM 2000005
using namespace std;
char a[DIM],b[DIM];
int ps[DIM],l1,l2,nP,ans[DIM];
void kmp() {
int q=0;
for(int i=0;i<l2;i++) {
while(q>0&&a[q]!=b[i])
q=ps[q-1];
if(a[q]==b[i])
q++;
if(q==l1)
ans[nP++]=i-l1+1;
}
}
void computePS() {
int j=0;
for(int i=1;i<l1;i++) {
while(j>0&&a[j]!=a[i])
j=ps[j-1];
if(a[j]==a[i])
j++;
ps[i]=j;
}
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin.getline(a,DIM);
fin.getline(b,DIM);
l1=strlen(a);
l2=strlen(b);
computePS();
kmp();
fout<<nP<<'\n';
for(int i=0;i<min(1000,nP);i++)
fout<<ans[i]<<" ";
return 0;
}