Pagini recente » Cod sursa (job #1736922) | Cod sursa (job #1814287) | Cod sursa (job #2348503) | Cod sursa (job #1641688) | Cod sursa (job #757394)
Cod sursa(job #757394)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXL 2000002
int prefix[MAXL], matches[1001];
char word[MAXL], search[MAXL];
int main()
{
FILE *in = fopen("strmatch.in", "r");
FILE *out = fopen("strmatch.out", "w");
int wordL, searchL, i, k;
fscanf(in, "%s\n%s", word, search);
wordL = strlen(word);
searchL = strlen(search);
k = -1;
prefix[0] = k;
for(i = 1; i < wordL; i++)
{
while(k != -1 && word[k + 1] != word[i]) k = prefix[k];
if(word[k + 1] == word[i]) k++;
prefix[i] = k;
}
k = -1;
matches[0] = 0;
for(i = 0; i < searchL && matches[0] < 1000; i++)
{
while(k != -1 && word[k + 1] != search[i]) k = prefix[k];
if(word[k + 1] == search[i]) k++;
if(k == wordL - 1)
{
k = prefix[k];
matches[++matches[0]] = i - wordL + 1;
}
}
fprintf(out, "%d\n", matches[0]);
for(i = 1; i <= matches[0]; i++) fprintf(out, "%d ", matches[i]);
fprintf(out, "\n");
fclose(in);
fclose(out);
return 0;
}