Pagini recente » Cod sursa (job #1933238) | Cod sursa (job #2896098) | Cod sursa (job #1309375) | Cod sursa (job #636258) | Cod sursa (job #1524852)
#include <iostream>
#include <fstream>
#include <cstring>
#define maxsize 2000100
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int urm[maxsize], sol[maxsize], n, m, nr;
char T[maxsize], P[maxsize];
void Prel(char *P)
{
int x, k=0;
urm[0]=0;
for(x=2; x<=m; x++)
{
while(k>0 && P[k+1]!=P[x]) k=urm[k];
if(P[k+1]==P[x]) k++;
urm[x]=k;
}
}
void KMP()
{
int i, k=0;
for(i=1; i<=n; i++)
{
while(k>0 && P[k+1]!=T[i]) k=urm[k];
if(P[k+1]==T[i])k++;
if(k==m)
{
++nr;
if (nr<1001) sol[nr]=i-m;
k=urm[k];
}
}
}
int main()
{
fin.getline(P+1,maxsize);
fin.getline(T+1,maxsize);
P[0]=T[0]='D';
m=strlen(P)-1; n=strlen(T)-1;
Prel(P);
KMP();
fout<<nr<<'\n';
nr=min(1000,nr);
for(int i=1; i<=nr; ++i)
fout<<sol[i]<<' ';
return 0;
}