Pagini recente » Cod sursa (job #1323986) | Cod sursa (job #2466797) | Cod sursa (job #2839025) | Cod sursa (job #2025253) | Cod sursa (job #1045993)
#include <iostream>
#include <fstream>
#include <string.h>
#define Nmax 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char t[Nmax],p[Nmax];
int n,m,urm[Nmax],c,v[Nmax];
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;
}
}
int main()
{
int i,x=-1;
f.getline(p,Nmax);
f.getline(t,Nmax);
n=strlen(t);
m=strlen(p);
urmatorul(p);
for(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)
{
x=urm[x];
++c;
v[c]=i-m+1;
}
}
g<<c<<"\n";
for(i=1;i<=c;++i) g<<v[i]<<" ";
return 0;
}