Pagini recente » Cod sursa (job #194096) | Cod sursa (job #682448) | Cod sursa (job #405717) | Cod sursa (job #2721448) | Cod sursa (job #1332768)
#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=0;
urm[1]=0;
for (i=2;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=0;
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)
{
d[++t]=i-m;
k=urm[k];
}
}
}
int main()
{
fin.getline(P+1,2000004);
fin.getline(T+1,2000004);
n=strlen(T+1);
m=strlen(P+1);
prefix();
kmp();
fout<<t<<'\n';
for (i=1;i<=min(1000,t);i++) fout<<d[i]<<" ";
fin.close();
fout.close();
return 0;
}