Pagini recente » Cod sursa (job #1979459) | Cod sursa (job #2014224) | Cod sursa (job #980449) | cel_mai_mare_olimpicar_2019_oni2008_zi2 | Cod sursa (job #3348402)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX=4e6+5;
string a, b, s;
int kmp[NMAX];
int main()
{
fin>>a>>b;
s=a+b;
// cout<<s<<'\n';
kmp[0]=0;
int cnt=0;
for(int i=1;i<s.size();i++){
int j=kmp[i-1];
while(s[i]!=s[j] && j!=0){
j=kmp[j-1];
}
kmp[i]=j;
if(s[i]==s[j])
kmp[i]++;
if(kmp[i]==a.size() && i-2*int(a.size())+1>0){
cnt++;
}
}
fout<<cnt<<'\n';
for(int i=0;i<s.size();i++){
if(kmp[i]==a.size() && i-2*int(a.size())+1>0){
fout<<i-2*int(a.size())+1<<" ";
}
}
return 0;
}