Pagini recente » Istoria paginii utilizator/analucaana | Cod sursa (job #757097) | Cod sursa (job #22101) | Istoria paginii runda/splunge7 | Cod sursa (job #1730755)
#include <iostream>
#include<fstream>
using namespace std;
string s1,s2;
int k,i,n,m,pi[2000005],cnt,rasp[1005];
ifstream f("strmatch.in");
ofstream g("strmatch.out");
void calcpref()
{
k=-1;pi[0]=-1;
for(i=1;i<n;i++)
{
while(k!=-1&&s1[i]!=s1[k+1])
k=pi[k];
if(s1[i]==s1[k+1]) k++;
pi[i]=k;
}
}
void kmp()
{
k=-1;
for(i=0;i<m;i++)
{
while(k!=-1&&s2[i]!=s1[k+1])
k=pi[k];
if(s1[k+1]==s2[i]) k++;
if(k==n-1)
{
cnt++;
k=pi[k];
if(cnt<=1000)rasp[cnt]=i-n+1;
}
}
}
int main()
{
f>>s1;
f>>s2;
n=s1.size();
m=s2.size();
calcpref();
kmp();
g<<cnt<<'\n';
for(i=1;i<=min(1000,cnt);i++) g<<rasp[i]<<' ';
return 0;
}