Pagini recente » Cod sursa (job #384681) | Cod sursa (job #1287353) | Cod sursa (job #3248351) | Cod sursa (job #222662) | Cod sursa (job #144359)
Cod sursa(job #144359)
#include <iostream>
#include <string>
#define mx 1<<21
using namespace std;
long i,h,n,m,p;
long pi[mx+4];
long v[1024];
char s1[mx+4],s2[mx+4];
void prefix()
{
pi[0]=0;
p=0;
for (i=1; i<=n; i++)
{
while (p>0 && s1[i]!=s1[p+1])
p=pi[p];
if (s1[i]==s1[p+1])
p++;
pi[i]=p;
}
}
void kmp()
{
n=strlen(s1)-1;
m=strlen(s2)-1;
prefix();
p=0;
h=0;
for (i=0; i<=m; i++)
{
while (p>0 && s2[i]!=s1[p+1])
p=pi[p];
if (s2[i]==s1[p+1])
p++;
if (p==m)
{
h++;
p=pi[p];
if (h<=1000)
v[h]=i-m;
}
}
}
int main(void)
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(s1+1,mx,stdin);
fgets(s2+1,mx,stdin);
kmp();
printf("%ld\n",h);
if (h>1000)
h=1000;
for (i=1; i<=h; i++)
printf("%ld",v[i]);
fclose(stdin);
fclose(stdout);
return 0;
}