Pagini recente » Cod sursa (job #63280) | Monitorul de evaluare | Cod sursa (job #1567467) | Cod sursa (job #742786) | Cod sursa (job #1514671)
#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;
int p[2000005],sol[1003],i,j,n,m,x,kmp;
char s1[2000005],s2[2000005];
string ss1,ss2;
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin>>ss1;
cin>>ss2;
// pi[1]=-1;
for(int i=0;i<ss1.size();i++)
{
n++;
s1[n]=ss1[i];
}
for(int i=0;i<ss2.size();i++)
{
m++;
s2[m]=ss2[i];
}
x=0;
for(i=2;i<=n;i++)
{
while(x>0&&s1[x+1]!=s1[i])
x=p[x];
if(s1[x+1]==s1[i])
x++;
p[i]=x;
}
x=0;
for(i=1;i<=m;i++)
{
while(kmp>0&&s1[kmp+1]!=s2[i])
kmp=p[kmp];
if(s1[kmp+1]==s2[i])
kmp++;
if(kmp==n)
{
sol[0]++;
if(sol[0]<=1000)
sol[sol[0]]=i-n;
}
}
cout<<sol[0]<<"\n";
for(i=1;i<=min(1000,sol[0]);i++)
cout<<sol[i]<<" ";
return 0;
}