Pagini recente » Cod sursa (job #989187) | Cod sursa (job #2248616) | Cod sursa (job #2428592) | Cod sursa (job #2143959) | Cod sursa (job #1389908)
#include <fstream>
#include <cstring>
#include <cstdio>
#define LGMAX 2000001
using namespace std;
ofstream fout("strmatch.out");
int d,lg,k,L[LGMAX],poz,nr,v[1001];
char a[LGMAX],b[LGMAX];
void prefix()
{
d=strlen(a);
L[0]=-1;
for(int i=1;i<d;i++)
{
k=L[i-1];
while(k>-1 && a[k+1]!=a[i])
k=L[k];
if(a[k+1]==a[i])
k++;
L[i]=k;
}
}
void kmp()
{
lg=strlen(b);
poz=-1;
for(int i=0;i<lg;i++)
{
while(poz>=0 && a[poz+1]!=b[i])
poz=L[poz];
if(a[poz+1]==b[i])
poz++;
if(poz==d-1)
{
nr++;
poz=L[poz];
if(nr<=1000)
v[nr]=i-d+1;
}
}
fout<<nr<<'\n';
for(int i=1;i<=nr && i<=1000;i++)
fout<<v[i]<<' ';
}
int main()
{
freopen("strmatch.in","r",stdin);
scanf("%s",&a);
scanf("%s",&b);
prefix();
kmp();
return 0;
}