Pagini recente » Cod sursa (job #2603713) | Cod sursa (job #1955301) | Cod sursa (job #3131363) | Cod sursa (job #1600683) | Cod sursa (job #2928587)
#include <bits/stdc++.h>
using namespace std ;
ifstream fin("strmatch.in") ;
ofstream fout("strmatch.out") ;
char s[2000001],pat[2000001] ;
int lps[2000001] ;
vector <int> v;
void makeprefix()
{
int n=strlen(pat) ;
lps[0]=0 ;
int i=1,j=0 ;
while(i<n)
{
if(pat[i]==pat[j])
j++,lps[i]=j,i++ ;
else
{
if(j) j=lps[j-1] ;
else
lps[i]=0,i++;
}
}
}
void KMP()
{
int i=0,j=0,n=strlen(pat),m=strlen(s);
while(m-i>=n-j)
{
if(pat[j]==s[i]) i++,j++ ;
if(j==n) v.emplace_back(i-n);
if(pat[j]!=s[i] && i<m)
{
if(j) j=lps[j-1] ;
else i++ ;
}
}
}
int main()
{
fin>>pat>>s ;
makeprefix() ;
KMP() ;
fout<<v.size()<<'\n' ;
for(int i=0; i<min(1000,(int)v.size()); ++i)
fout<<v[i]<<" " ;
return 0 ;
}