Pagini recente » Cod sursa (job #3000853) | Cod sursa (job #1748744) | Cod sursa (job #4324) | Cod sursa (job #2847618) | Cod sursa (job #674089)
Cod sursa(job #674089)
#include <stdio.h>
#define min(a, b) ((a < b) ? a : b)
#define NMAX 2000000
char s1[NMAX], s2[NMAX];
int table[NMAX], where[1000];
void t() {
table[0] = -1;
int k = -1;
int i;
for (i = 1; s1[i] != '\0'; i++)
{
while (k > -1 && s1[k + 1] != s1[i])
k = table[k];
if (s1[i] == s1[k + 1])
k++;
table[i] = k;
}
}
int main () {
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w", stdout);
gets(s1);
gets(s2);
t();
int i;
int j = -1, count = 0;
for (i = 0; s2[i] != '\0'; i++)
{
while (j > -1 && s1[j + 1] != s2[i])
j = table[j];
if (s2[i] == s1[j + 1])
j++;
if (s1[j + 1] == '\0')
{
count ++;
if (count <= 1000)
where[count - 1] = i - j;
j = table[j];
}
}
printf ("%d\n", count);
for (i = 0; i < min(count, 1000); i++)
printf ("%d ", where[i]);
return 0;
}