Pagini recente » Cod sursa (job #1252351) | Cod sursa (job #2454157) | Cod sursa (job #2946117) | Cod sursa (job #2504248) | Cod sursa (job #2810096)
#include <bits/stdc++.h>
using namespace std;
string A,B;
vector <int> poz;
int pi[2000005],pr=0,n,m;
static void prefixe(){
int 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;
n=A.size();
m=B.size();
A.insert(A.begin(),' ');
B.insert(B.begin(),' ');
prefixe();
int q=0;
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==n){
q=pi[n];
if(poz.size()<1000)
poz.push_back(i-n);
pr++;
}
}
cout<<pr<<"\n";
for(auto e:poz)
cout<<e<<" ";
}