Pagini recente » Cod sursa (job #2270955) | Cod sursa (job #2725092) | Cod sursa (job #515534) | Cod sursa (job #1223185) | Cod sursa (job #1467986)
/*Potrivirea sirurilor - KMP*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define NMAX 2000005
char sir1[NMAX], sir2[NMAX];
int i, j, k, n, m, rez[1005];
int *prefix(char *sir)
{
int l = strlen(sir);
int i = 0, j;
int *pre = (int *)calloc(l, sizeof(int));
pre[0] = j = -1;
for(i = 1; i<l; ++i)
{
while(j > -1 && sir[j+1] != sir[i])
j = pre[j];
if(sir[j+1] == sir[i])
++j;
pre[i] = j+1;
}
return pre;
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", sir1);
scanf("%s", sir2);
n = strlen(sir1);
m = strlen(sir2);
int *p = prefix(sir1);
/*printf("%s %d\n", sir1, n);
printf("%s %d\n", sir2, m);
for(i = 0; i<n; ++i)
printf("%d ", p[i]);*/
j = -1;
for(i = 0; i < m; ++i)
{
while( j> -1 && sir1[j+1] != sir2[i])
j = p[j];
if(sir1[j+1] == sir2[i])
++j;
if(j + 1 == n)
{
j = p[j];
if(++k > 1000)
break;
else
rez[k] = i - n + 1;
}
}
printf("%d\n", k);
for(i = 1; i <= k; ++i)
printf("%d ", rez[i]);
free(prefix);
return 0;
}