Pagini recente » Cod sursa (job #175290) | Cod sursa (job #2890378) | Cod sursa (job #3266268) | Cod sursa (job #2599680) | Cod sursa (job #2810093)
#include <bits/stdc++.h>
using namespace std;
string A,B;
vector <int> poz;
int pi[2000001],pr=0;
static void prefixe(){
int n=A.size(),q=0;
pi[1]=0;
for(int i=2;i<n;++i){
while(q && A[q+1]!=A[i])
q=pi[q];
if(A[q+1]==A[i])
++q;
pi[i]=q;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>A>>B;
A.insert(A.begin(),' ');
B.insert(B.begin(),' ');
prefixe();
int q=1,m=B.size()-1;
for(int i=1;i<=m;++i){
while(q && A[q+1]!=B[i])
q=pi[q];
if(A[q+1]==B[i])
++q;
if(q==A.size()-1){
q=pi[A.size()-1];
if(poz.size()<1000)
poz.push_back(i-A.size()+1);
pr++;
}
}
cout<<pr<<"\n";
for(auto e:poz)
cout<<e<<" ";
}