Pagini recente » Cod sursa (job #480060) | Cod sursa (job #1055360) | Cod sursa (job #1490151) | Cod sursa (job #1121763) | Cod sursa (job #1486684)
#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];
void preKmp(string x)
{
int n=x.length()-1;
int k=0;
kmpNext[0]=0;
for(int i=2;i<=n;++i)
{
while(k>0 && x[i]!=x[k+1])
k=kmpNext[k];
if(x[i]==x[k+1])
k++;
kmpNext[i]=k;
}
}
void KMP(string k)
{
int i;
preKmp(k);
int q=0;
for(int i=1;i<s.length();++i)
{
while(q>0 && k[q+1]!=s[i]) q=kmpNext[q];
if(k[q+1]==s[i])
q++;
if(q==k.length()-1)
{
if(match.size()<1000)
match.push_back(i-q);
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>p>>s;
p=' '+p;
s=' '+s;
KMP(p);
sort(match.begin(),match.end());
cout<<match.size()<<"\n";
for(int i=0;i<match.size();++i)
{
if(i)
cout<<" "<<match[i];
else
cout<<match[i];
}
return 0;
}