Pagini recente » Cod sursa (job #2146438) | Cod sursa (job #2539782) | Cod sursa (job #2341225) | Monitorul de evaluare | Cod sursa (job #3309093)
//#include <iostream>
#include <fstream>
#include <stack>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char s[2000005];
char w[2000005];
int T[2000005],q,R[2002],k,n,m;
void prefixe()
{
for(int i=2,q=0;i<=m;i++)
{
while(q && w[q+1]!=w[i]) q=T[q];
if(w[q+1]==w[i]) q++;
T[i]=q;
}
}
int main()
{
int q=0;
cin>>w>>s; n=strlen(s),m=strlen(w);
for(int i=n;i>0;i--) s[i]=s[i-1];
for(int i=m;i>0;i--) w[i]=w[i-1];
s[0]=w[0]=' ';
prefixe();
for(int i=1;i<=n;i++)
{
while(s[i]!=w[q+1] && q) q=T[q];
if(w[q+1]==s[i]) q++;
if(q==m)
{
q=T[q];
++k;
if(k<=1000) R[k]=i-m;
}
}
cout<<k<<endl;
for(int i=1;i<=k;i++) cout<<R[i]<<" ";
return 0;
}