Pagini recente » Cod sursa (job #597405) | Cod sursa (job #1751447) | Cod sursa (job #233623) | Cod sursa (job #2619113) | Cod sursa (job #2795342)
#include <bits/stdc++.h>
#define N 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char P[N], T[N];
int a[N],urm[N],n,m,k;
void Prefix()
{
int i,j=0;
for(i=1;i<n;i++)
{
while(j>0&&P[i]!=P[j]) j=urm[j-1];
if(P[i]==P[j]) j++;
urm[i]=j;
}
}
void KMP()
{
int q=0;
for(int i=0;i<m;i++)
{
while(q>0&&P[q]!=T[i]) q=urm[q-1];
if(P[q]==T[i]) ++q;
if(q==n)
{
a[k++]=i-n+1;
}
}
}
int main()
{
fin.getline(P,N);///pattern
fin.getline(T,N);///Text
n=strlen(P);
m=strlen(T);
Prefix();
KMP();
fout<<k<<'\n';
for(int i=0;i<k;i++)fout<<a[i]<<' ';
return 0;
}