Pagini recente » Cod sursa (job #170042) | Cod sursa (job #1741745) | Cod sursa (job #2186281) | Cod sursa (job #2851684) | Cod sursa (job #1467991)
/*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 = 0;
int *pre = (int *)calloc(l+1, sizeof(int));
for(i = 2; i<=l; ++i)
{
while(j && sir[j+1] != sir[i])
j = pre[j];
if(sir[j+1] == sir[i])
++j;
pre[i] = j;
}
return pre;
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
//char *sir1 = (char *)calloc(NMAX, sizeof(char));
//char *sir2 = (char *)calloc(NMAX, sizeof(char));
scanf("%s", sir1);
scanf("%s", sir2);
n = strlen(sir1);
m = strlen(sir2);
memcpy(sir1 + 1, sir1, n*sizeof(char));
memcpy(sir2 + 1, sir2, m*sizeof(char));
int *p = prefix(sir1);
j = 0;
for(i = 1; i <= m; ++i)
{
while( j && sir1[j+1] != sir2[i])
j = p[j];
if(sir1[j+1] == sir2[i])
++j;
if(j == n)
{
j = p[j];
if(++k > 1000)
break;
else
rez[k] = i - n;
}
}
printf("%d\n", k);
for(i = 1; i <= k; ++i)
printf("%d ", rez[i]);
printf("\n");
free(prefix);
//free(sir1);
//free(sir2);
return 0;
}