Pagini recente » Cod sursa (job #677347) | Cod sursa (job #3280600) | Cod sursa (job #284243) | Cod sursa (job #2707481) | Cod sursa (job #3347748)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
string a,b,s;cin>>a>>b;
s=a+'#'+b;
int kmp[s.length()];
kmp[0]=0;
for(int i=1;i<s.length();i++){
kmp[i]=kmp[i-1];
while(kmp[i]>0 && s[i]!=s[kmp[i]]){
kmp[i]=kmp[kmp[i]-1];
}
if(s[i]==s[kmp[i]]){
kmp[i]=kmp[i]+1;
}
}
int v=a.length();
int cnt=0;
queue<int> q;
for(int i=0;i<s.length();i++){
if(kmp[i]==v){
cnt++;
q.push(i-(2*a.length()));
}
}
cout<<cnt<<'\n';
while(!q.empty()){
cout<<q.front()<<' ';
q.pop();
}
}