Pagini recente » Cod sursa (job #2569986) | Cod sursa (job #2555113) | Cod sursa (job #2307337) | Cod sursa (job #2940250) | Cod sursa (job #362500)
Cod sursa(job #362500)
#include <fstream>
#include <cstring>
#define nMax 2000002
using namespace std;
ifstream f("kmp.in");
ofstream g("kmp.out");
int urm [nMax];
char T[nMax], P[nMax];
int n,m,ap,v[1001];
void citire ()
{
f.getline (P+1,256); m=strlen (P+1);
f.getline (T+1,1001); n=strlen (T+1);
f.close ();
}
void prefix (char *p)
{
int k=0, x;
urm[1]=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;
}
}
int main ()
{
citire ();
int i, x=0;
prefix (P);
for (i=1; i<=n; i++)
{
while (x>0 && P[x+1]!=T[i]) x=urm[x];
if (P[x+1]==T[i]) x++; //s-au potrivit
if (x==m)
{
v[++ap]=i-m;
x=urm[x];
}
}
g<<ap<<'\n';
for (i=1; i<=ap; i++)
g<<v[i]<<" ";
g.close (); return 0;
}