Pagini recente » Cod sursa (job #221629) | Cod sursa (job #1830764) | Cod sursa (job #54464) | Cod sursa (job #2687582) | Cod sursa (job #1949864)
#include <iostream>
#include <fstream>
#include <cstring>
#define LMAX 2000000
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[LMAX],b[LMAX];
int pref[LMAX],n,m,sol[1001],nr;
void prefix()
{
int k=0;
for(int i=2; i<=n;i++){
while(k>0 && a[k+1]!=a[i])
k=pref[k];
if(a[k+1]==a[i])
k++;
pref[i]=k;
}
}
void kmp()
{
int k=0;
pref[1]=0;
for(int i=1;i<=m;i++){
while(k>0 && a[k+1]!=b[i])
k=pref[k];
if(a[k+1]==b[i])
k++;
if(k==n){
nr++;
if(nr<=1000)
sol[nr]=i-k;
k=pref[k];
}
}
}
int main()
{
fin.getline(a+1,sizeof(a));
fin.getline(b+1,sizeof(a));
n=strlen(a+1);
m=strlen(b+1);
prefix();
kmp();
fout<<nr<<'\n';
for(int i=1; i<=nr; i++)
fout<<sol[i]<<' ';
return 0;
}