Pagini recente » Cod sursa (job #553642) | Cod sursa (job #797813) | Cod sursa (job #1990810) | Cod sursa (job #1968095) | Cod sursa (job #3352040)
///KMP
#include <bits/stdc++.h>
using namespace std;
int LPS[2000005];
int cnt=0,poz[2000005];
string f,s;
void generateLPS()
{
int pref=0;
for(size_t suf=1; suf<f.size(); suf++)
{
while(pref!=0 && f[pref]!=f[suf])
{
pref=LPS[pref-1];
}
if(f[pref]==f[suf])
{
pref++;
}
LPS[suf]=pref;
}
}
void findStr()
{
size_t j=0;
for(size_t i=0; i<s.size(); i++)
{
while(j!=0 && f[j]!=s[i])
{
j=LPS[j-1];
}
if(s[i]==f[j])
{
j++;
if(j==f.size() && cnt<1000)
{
cnt++;
poz[cnt]=i-j+1;
j=LPS[j-1];
}
}
}
}
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin>>f>>s;
generateLPS();
findStr();
cout<<cnt<<'\n';
for(int i=1;i<=cnt;i++)
{
cout<<poz[i]<<' ';
}
return 0;
}