Pagini recente » Cod sursa (job #1603038) | Cod sursa (job #1199126) | Cod sursa (job #1971381) | Cod sursa (job #1872861) | Cod sursa (job #3329777)
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> prefix_function(const string &s){
int n = s.size();
vector<int> pi(n);
for(int i=1;i<n;i++){
int j=pi[i-1];
while(j>0 && s[i]!=s[j]) j=pi[j-1];
if(s[i]==s[j]) j++;
pi[i]=j;
}
return pi;
}
signed 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; cin>>A>>B;
vector<int> pi = prefix_function(A);
vector<int> occ;
int j=0;
for(int i=0;i<(int)B.size();i++){
while(j>0 && B[i]!=A[j]) j=pi[j-1];
if(B[i]==A[j]) j++;
if(j==(int)A.size()){
occ.push_back(i-(int)A.size()+1);
j=pi[j-1];
}
}
cout<<occ.size()<<"\n";
for(int i=0;i<min((int)occ.size(),1000LL);i++){
cout<<occ[i]<<" ";
}
cout<<"\n";
return 0;
}