Pagini recente » Cod sursa (job #2899684) | Cod sursa (job #3294698) | Cod sursa (job #2127008) | Cod sursa (job #530838) | Cod sursa (job #1012561)
#include<stdio.h>
#include<string.h>
using namespace std;
#define Nmax 2000005
char s[Nmax],p[Nmax];
int k, m, n,D[Nmax],px[Nmax];
void citire()
{
freopen("strmatch.in","r",stdin);
s[0]=p[0]=' ';
gets(s+1);
gets(p+1);
fclose(stdin);
n=strlen(s+1);
m=strlen(p+1);
}
void prefix(char s[])
{
int i;
px[1]=0;
k=0;
for(i=2;i<=n;++i)
{
//k=px[i-1];
while(k>0&&s[k+1]!=s[i])
k=px[k];
if(s[k+1]==s[i])
k++;
px[i]=k;
// printf("%c\n", s[i]);
}
}
void kmp(char s[], char p[])
{
int i;
prefix(s);
k=0;
for(i=1;i<=m;i++)
{
while(k>0&&s[k+1]!=p[i])
k=px[k];
if(s[k+1]==p[i])
k++;
if(k==n)
{
D[++D[0]]=i-n;
//k=px[k];
}
}
}
void afisare()
{
int i;
freopen("strmatch.out","w",stdout);
printf("%d\n", D[0]);
int pana=D[0];
if(D[0]>1000)
pana=1000;
for(i=1;i<=pana;i++)
printf("%d ",D[i]);
printf("\n");
fclose(stdout);
}
int main()
{
citire();
prefix(s);
kmp(s,p);
afisare();
return 0;
}