Pagini recente » Cod sursa (job #3002893) | Cod sursa (job #578845) | Cod sursa (job #1610188) | Cod sursa (job #2956709) | Cod sursa (job #1524706)
#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 Urmatorul(char *P)
{
int k=-1, x;
urm[0]=0;
for (x=1; 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 x=-1;
for (int i=0; i<n; ++i)
{
while (x>0 && P[x+1]!=T[i]) x=urm[x];
if (P[x+1]==T[i]) x++;
if (x==m-1)
{
++nr;
if (nr<1002) sol[nr]=i-m+1;
x=urm[x];
}
}
}
int main()
{
fin.getline(P,maxsize); m=strlen(P);
fin.getline(T,maxsize); n=strlen(T);
Urmatorul(P);
KMP();
fout<<nr<<'\n';
nr=min(1000,nr);
for (int i=1; i<=nr; ++i)
fout<<sol[i]<<" ";
return 0;
}