Pagini recente » Cod sursa (job #605892) | Cod sursa (job #137590) | Cod sursa (job #2792719) | Cod sursa (job #2663774) | Cod sursa (job #2928599)
#include <bits/stdc++.h>
using namespace std ;
ifstream fin("strmatch.in") ;
ofstream fout("strmatch.out") ;
string s,pat ;
int urm[2000001] ;
vector <int> v ;
void makeprefix()
{
int k=-1 ;
urm[0]=0 ;
for(int i=1; i<pat.size(); ++i)
{
while(k>0 && pat[i]!=pat[k+1]) k=urm[k] ;
if(pat[i]==pat[k+1]) k++ ;
urm[i]=k ;
}
}
void KMP()
{
int k=-1 ;
for(int i=1; i<s.size(); ++i)
{
while(k>0 && pat[k+1]!=s[i]) k=urm[k] ;
if(pat[k+1]==s[i]) k++ ;
if(k==pat.size()-1) v.push_back(i-pat.size()+1) ;
}
}
int main()
{
fin>>pat>>s ;
makeprefix() ;
KMP() ;
fout<<v.size()<<'\n' ;
for(int i=0; i<min((int)v.size(),1000); ++i)
fout<<v[i]<<" " ;
return 0 ;
}