Pagini recente » Cod sursa (job #1139882) | Cod sursa (job #2749419) | Cod sursa (job #336552) | Cod sursa (job #1027353) | Cod sursa (job #1332744)
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int n,m,i,urm[2000005],d[2000001],t;
char T[2000005],P[2000005];
void prefix()
{
int i,k=-1;
urm[0]=0;
for (i=1;i<m;i++)
{
while (k>0&&P[k+1]!=P[i]) k=urm[k];
if (P[k+1]==P[i]) k++;
urm[i]=k;
}
}
void kmp()
{
int i,k=-1;
for (i=0;i<n;i++)
{
while (k>0&&P[k+1]!=T[i]) k=urm[k];
if (P[k+1]==T[i]) k++;
if (k==m-1) d[++t]=i-m+1;
}
}
int main()
{
fin.getline(P,2000001);
fin.getline(T,2000001);
n=strlen(T);
m=strlen(P);
prefix();
kmp();
fout<<t<<'\n';
for (i=1;i<=min(1000,t);i++) fout<<d[i]<<" ";
fin.close();
fout.close();
return 0;
}