Pagini recente » Cod sursa (job #1436887) | Cod sursa (job #3274004) | Cod sursa (job #2598594) | Cod sursa (job #406701) | Cod sursa (job #2353466)
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;
string a, b;
int lp[2000005], la, lb;
vector <int> sol;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.ou","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]<<" ";
*/
cout<<sol.size()<<"\n";
for(int i : sol)
cout<<i<<" ";
return 0;
}