Pagini recente » Cod sursa (job #1598928) | Cod sursa (job #2949293) | Cod sursa (job #1863676) | Cod sursa (job #1007041) | Cod sursa (job #1486690)
#include <bits/stdc++.h>
#define M 2000100
using namespace std;
inline int MAX(int a,int b){return (a>b)?a:b;}
inline int MIN(int a,int b){return (a<b)?a:b;}
int t,n;
string s,p;
vector<int> match;
int kmpNext[M];
int cnt;
void preKmp(string x)
{
int k;
kmpNext[0]=-1;
for(int i=0;i<x.length();++i)
{
k=kmpNext[i];
while(k>-1 && x[i]!=x[k])
k=kmpNext[k];
kmpNext[i+1]=k+1;
}
}
void KMP(string p)
{
int n=s.length();
int m=p.length();
cnt=0;
preKmp(p);
int k=0,i=0;
while(i<n)
{
if(k==-1)
{
++i;
k=0;
}
else if(p[k]==s[i])
{
++i;
++k;
if(k==m)
{
if(cnt<1000)
match.push_back(i-m);
++cnt;
k=kmpNext[k];
}
}
else
k=kmpNext[k];
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>p;
cin>>s;
KMP(p);
cout<<cnt<<"\n";
for(int i=0;i<cnt;++i)
{
cout<<match[i]<<" ";
}
cout<<"\n";
return 0;
}