Pagini recente » Cod sursa (job #1241821) | Cod sursa (job #1990864) | Cod sursa (job #216835) | Cod sursa (job #2366569) | Cod sursa (job #409168)
Cod sursa(job #409168)
#include<stdio.h>
#include<string.h>
#include<fstream>
using namespace std;
#define Nmax 2000001
char s[Nmax],p[Nmax];
int k, m, n,D[1001],px[1001];
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);
for(k=0,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<=D[0];i++)
printf("%d ",D[i]);
fclose(stdout);
}
int main()
{
citire();
kmp(s,p);
afisare();
return 0;
}