Pagini recente » Cod sursa (job #3186279) | Cod sursa (job #2461846) | Cod sursa (job #1549636) | Cod sursa (job #1916730) | Cod sursa (job #1458033)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXL 2000000
int word_length, string_length, candidate, table[MAXL], n[1000], N;
char word[MAXL], string[MAXL];
int main()
{
int i, j;
// open files
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
// read strings
scanf("%[^\n]", word); getchar();
scanf("%[^\n]", string); getchar();
word_length = strlen(word);
string_length = strlen(string);
if (word_length > string_length)
{
printf("0\n");
return 0;
}
// bake partial match table
table[0] = -1;
i = 2;
while (i < word_length)
{
// match
if (word[i - 1] == word[candidate])
{
candidate++;
table[i] = candidate;
i++;
}
// fall back
else if (candidate > 0)
{
candidate = table[candidate];
}
// mismatch
else
{
table[i] = 0;
i++;
}
}
/*
// print table
for (i = 0; i < word_length; i++)
{
printf("%d", table[i]);
}
*/
// search for matches
i = 0;
j = 0;
while (i + word_length <= string_length)
{
// match
if (word[j] == string[i + j])
{
if (j == word_length - 1)
{
if (N < 1000) n[N] = i;
N++;
i += j - table[j];
}
else j++;
}
// advance (from table)
else if (table[j] > -1)
{
i += j - table[j];
j = table[j];
}
// advance one position
else
{
j = 0;
i++;
}
}
// print results
printf("%d\n", N);
for (i = 0; i < N && i < 1000; i++)
{
printf("%d ", n[i]);
}
return 0;
}