Pagini recente » Cod sursa (job #560409) | Cod sursa (job #1075287)
#include<stdio.h>
#include <stdlib.h>
#include<string.h>
#define MAXN 2000005
int m, i, n, nrsol;
int p[MAXN], sol[1001];
char s1[MAXN], s2[MAXN];
void prefix()
{
int k = 0, i;
for (i = 2; i <= m; i++)
{
while (k > 0 && s2[k + 1] != s2[i])
k = p[k];
if (s2[k + 1] == s2[i])
k++;
p[i] = k;
}
}
void kmp()
{
int i, k = 0;
for (i = 1; i <= n; i++)
{
while (k > 0 && s2[k + 1] != s1[i])
k = p[k];
if (s2[k + 1] == s1[i])
k++;
if (k == m)
{
nrsol++;
if (nrsol <= 1000)
sol[nrsol] = i - m;
k = p[m];
}
}
}
int main()
{
FILE *f = fopen("strmatch.in", "r"), *g = fopen("strmatch.out", "w");
fscanf(f,"%s%s", s2 + 1, s1 + 1);
s2[0] = ' ';
s1[0] = ' ';
m = strlen(s2) - 1;
n = strlen(s1) - 1;
prefix();
kmp();
fprintf(g,"%d\n", nrsol);
for (i = 1; i <= nrsol&&i <= 1000; i++)
fprintf(g,"%d ", sol[i]);
return 0;
}