Pagini recente » Cod sursa (job #2137865) | Cod sursa (job #1928072) | Cod sursa (job #2689652) | Cod sursa (job #1604129) | Cod sursa (job #553393)
Cod sursa(job #553393)
#include <stdio.h>
#include <string.h>
#define nmax 2000010
using namespace std;
char A[nmax],B[nmax];
int n,m, b[nmax], p[nmax], N;
void Citire()
{
freopen("strmatch.in","r",stdin);
scanf("%s%s",&A,&B);
n = strlen(A);
m = strlen(B);
}
void Form()
{
b[0]=-1;
int i=0, j=-1;
while(i<n)
{
while(j>=0 && A[i]!=A[j])
j=b[j];
i++, j++;
b[i]=j;
}
}
void Kmp()
{
int i=0, j=0;
while(i<m)
{
while(j>=0 && B[i]!=A[j])
j=b[j];
i++, j++;
if(j==n)
{
N++;
p[N]=i-j;
j=b[j];
}
}
}
void Afis()
{
freopen("strmatch.out","w",stdout);
printf("%d\n",N);
for(int k=1;k<=1000 && k<=N;k++)
printf("%d ",p[k]);
printf("\n");
}
int main()
{
Citire();
Form();
Kmp();
Afis();
return 0;
}