Pagini recente » Cod sursa (job #1995646) | Cod sursa (job #3325744) | Cod sursa (job #893648) | Cod sursa (job #3318081) | Cod sursa (job #3331876)
#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.size()];
kmp[0]=0;
for(int i=1;i<S.size();i++){
kmp[i]=kmp[i-1];
while(kmp[i]>0 && S[kmp[i]]!=S[i]){
kmp[i]=kmp[kmp[i]-1];
}
if(S[kmp[i]]==S[i]){
kmp[i]++;
}
}
int cnt=0;
queue<int> q;
for(int i=A.length()+1;i<S.length();i++){
if(kmp[i]==A.size()){
cnt++;
q.push(i-(2*A.length()));
}
}
cout<<cnt<<'\n';
while(!q.empty()){
cout<<q.front()<<" ";
q.pop();
}
}