Pagini recente » Cod sursa (job #3038288) | Cod sursa (job #2946333) | Cod sursa (job #695012) | Cod sursa (job #1939212) | Cod sursa (job #2353601)
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;
string a, b;
int lp[2000005], la, lb;
vector <int> sol;
char *p;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
getline(cin,a);
getline(cin,b);
la=a.length();
lb=b.length();
int k=0;
for(int i=1 ; i<la; ++i){
if(a[k]==a[i])
lp[i] = ++k;
else{
--k;
//k=lp[k];
while(k>=0){
k=lp[k];
if(a[k]==a[i]){
lp[i]=++k;
break;
}
--k;
}
if(k<0)
lp[i]=0, k=0;
}
}
k=0;
for(int i=0;i<lb;++i){
if(k==la){
sol.push_back(i-la);
k=lp[k-1];
}
if(a[k]==b[i])
++k;
else{
k--;
while(k>0){
k=lp[k];
if(a[k]==b[i]){
++k;
break;
}
--k;
}
if(k<0)
k=0;
}
}
if(k==la){
sol.push_back(lb-la);
}
/*
for(int i=0;i<la;++i)
cout<<lp[i]<<" ";
*/
la = sol.size();
cout<<la<<"\n";
la = min(la,1000);
for(int i = 0; i < la; ++i)
cout<<sol[i]<<" ";
return 0;
}