Pagini recente » Cod sursa (job #2617505) | Cod sursa (job #1326323) | Cod sursa (job #2268054) | Cod sursa (job #2628624) | Cod sursa (job #2928582)
#include <bits/stdc++.h>
using namespace std ;
ifstream fin("strmatch.in") ;
ofstream fout("strmatch.out") ;
string s,pat ;
int lps[101] ;
vector <int> v;
void makeprefix()
{
lps[0]=0 ;
int i=1,j=0 ;
while(i<pat.size())
{
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;
while(s.size()-i>=pat.size()-j)
{
if(pat[j]==s[i]) i++,j++ ;
if(j==pat.size()) v.push_back(i-pat.size());
if(pat[j]!=s[i] && i<s.size())
{
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 ;
}