Pagini recente » Cod sursa (job #1307114) | Cod sursa (job #1964437) | Cod sursa (job #2070624) | Cod sursa (job #1303471) | Cod sursa (job #2038409)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
char N[2000001],H[2000001],c;
int n,h,s[2000001],sol[1001],v;
int k,f;
int main()
{
in>>N+1;
n=strlen(N+1);
///se construieste S
s[0]=-1;
s[1]=0;
for(int i=2;i<=n;i++)
{
///se calculeaza s[i]
k=i-1;
c=N[i];
while (s[k]!=-1 && N[s[k]+1]!=c)
k=s[k];
s[i]=s[k]+1;
}
in>>H+1;
h=strlen(H+1);
f=0;
for(int i=1;i<=h;i++)
{
while (f!=-1)
if (N[f+1]==H[i])
break;
else f=s[f];
if(f==-1)
f=0;
else
{
f++;
if(f==n)
{
if(v<1000)
{
v++;
sol[v]=i-n;
}
f=s[f];
}
}
}
out<<v<<endl;
for(int i=1;i<=v;i++)
out<<sol[i]<<" ";
}