Pagini recente » Cod sursa (job #1707115) | Cod sursa (job #2033078) | Cod sursa (job #1872527) | Cod sursa (job #2377977) | Cod sursa (job #248556)
Cod sursa(job #248556)
#include <stdio.h>
#include <string.h>
#define nmax 2000002
char pattern[nmax], text[nmax];
int i, k, lp, lt, L[nmax], matches[1024];
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", pattern+1, text+1);
for (text[0] = pattern[0] = ' ', i = 2, lp = strlen(pattern); i <= lp; ++i)
{
k = L[i-1];
while (k > 0 && pattern[k+1] != pattern[i]) k = L[k];
if (pattern[k+1] == pattern[i]) k++;
L[i] = k;
}
for (k = 0, i = 1, lt = strlen(text); i <= lt; ++i)
{
while (k > 0 && pattern[k+1] != text[i]) k = L[k];
if (pattern[k+1] == text[i]) k++;
if (k == lp-1)
{
++matches[0];
if (matches[0] <= 1000)
matches[matches[0]] = i-k;
k = L[k];
}
}
printf("%d\n", matches[0]);
if (matches[0] > 0)
{
for (i = 1; i < (matches[0] > 1000? 1000: matches[0]); printf("%d ", matches[i]), ++i);
printf("%d\n", matches[i]);
}
}