Pagini recente » Cod sursa (job #1864243) | Cod sursa (job #843384) | Cod sursa (job #2052822) | Cod sursa (job #844759) | Cod sursa (job #3348401)
#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()){
cnt++;
}
}
fout<<cnt<<'\n';
for(int i=0;i<s.size();i++){
if(kmp[i]==a.size()){
fout<<i-2*int(a.size())+1<<" ";
}
}
return 0;
}