Pagini recente » Cod sursa (job #569259) | Cod sursa (job #1552541) | Cod sursa (job #2587825) | Cod sursa (job #3263397) | Cod sursa (job #409148)
Cod sursa(job #409148)
#include<stdio.h>
#include<string.h>
#include<fstream>
using namespace std;
#define Nmax 2000001
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 found(int d)
{
D[0]=D[0]+1;
if(D[0]<=1000)
D[D[0]]=d;
}
void prefix(char s[])
{
int i;
px[1]=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;
}
}
void kmp(char s[], char p[])
{
int i;
prefix(s);
k=0;
for(i=1;i<=n;i++)
{
while(k>0&&s[k+1]!=p[i])
k=px[k];
if(s[k+1]==p[i])
k++;
if(k==m)
{
found(i-m);
k=px[k];
}
}
}
void afisare()
{
int i;
freopen("strmatch.out","w",stdout);
printf("%d\n", D[0]);
for(i=1;i<=1000&&i<=D[0];i++)
printf("%d ",D[i]);
fclose(stdout);
}
int main()
{
citire();
kmp(s,p);
afisare();
return 0;
}