Pagini recente » Cod sursa (job #2782528) | Cod sursa (job #1427320) | Cod sursa (job #3236040) | Cod sursa (job #845524) | Cod sursa (job #409162)
Cod sursa(job #409162)
#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],nr=0;
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)
{
nr++;
if(nr<=1000)
D[nr]=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", nr);
for(i=1;i<=1000&&i<=nr;i++)
printf("%d ",D[i]);
fclose(stdout);
}
int main()
{
citire();
kmp(s,p);
afisare();
return 0;
}