Pagini recente » Cod sursa (job #2256042) | Cod sursa (job #1439578) | Cod sursa (job #2382739) | Cod sursa (job #727138) | Cod sursa (job #501195)
Cod sursa(job #501195)
#include<fstream>
#include<string.h>
using namespace std;
char t[2000001],p[2000001];
int u[2000001],n,m,s[1001];
int main()
{ifstream in("strmatch.in");
ofstream w("strmatch.out");
in>>p>>t;
int i,k=0,q;
m=strlen(p);
n=strlen(t);
int zx,zy=-1;
u[0]=-1;
for(zx=1;zx<m;++zx)
{while(zy>-1&&p[zy+1]!=p[zx])
zy=u[zy];
if(p[zy+1]==p[zx])
zy++;
u[zx]=zy;}
q=-1;
for(i=0;i<n;++i)
{while(q>-1&&p[q+1]!=t[i])
q=u[q];
if(p[q+1]==t[i])
q++;
if(q==m-1)
{k++;
if(k<=1000)
s[k]=i-m+1;
q=u[q];}}
w<<k<<"\n";
for(i=1;i<=k&&i<=1000;++i)
w<<s[i]<<" ";
return 0;
}