Pagini recente » Clasament puh | Cod sursa (job #2087415) | Cod sursa (job #2799053) | Cod sursa (job #2458387) | Cod sursa (job #2938356)
#include <bits/stdc++.h>
using namespace std ;
ifstream fin("strmatch.in") ;
ofstream fout("strmatch.out") ;
#define NMAX 2000001
char a[NMAX],b[NMAX];
vector <int> v ;
int pi[NMAX],n,m;
void make_prefix()
{
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()
{
fin>>a+1>>b+1 ;
n=strlen(a+1),m=strlen(b+1) ;
make_prefix() ;
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) v.push_back(i-n) ;
}
fout<<v.size()<<'\n' ;
for(int i=0; i<min(1000,(int)v.size()); ++i) fout<<v[i]<<" " ;
return 0 ;
}