Pagini recente » Istoria paginii runda/cnamd | Cod sursa (job #881330) | Monitorul de evaluare | Statisticile problemei Yamstp | Cod sursa (job #1707064)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
#define Nmax 2000005
string N,M;
int k,pi[Nmax],q,m,n,nr,pos[Nmax];
void make_prefix(){
pi[1]=0;
for(int i=2;i<=n;i++){
while(k && N[i+1]!=N[i]){
k=pi[k];
}
if(N[k+1]==N[i])
k++;
pi[i]=k;
}
}
void alg_KMP(){
for(int i=1;i<=m;i++){
while(q && N[q+1]!=M[i])
q=pi[q];
if(N[q+1] == M[i])
q++;
if(q == n){
q=pi[n];
nr++;
if(nr <= 1000)
pos[nr]=i-n;
}
}
}
int main()
{
getline(in,N);
getline(in,M);
n=N.size();
m=M.size();
make_prefix();
alg_KMP();
out<<nr<<'\n';
for(int i=1;i<=min(nr,1000);i++)
out<<pos[i]<<" ";
return 0;
}