Mai intai trebuie sa te autentifici.
Cod sursa(job #248538)
Utilizator | Data | 26 ianuarie 2009 00:06:26 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 26 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.86 kb |
#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[++matches[0]] = i-k;
k = L[k];
if (matches[0] >= 1000) break;
}
}
printf("%d\n", matches[0]);
for (i = 1; i < matches[0]; printf("%d ", matches[i]), ++i);
printf("%d\n", matches[i]);
}