Pagini recente » tema | Cod sursa (job #670093) | Cod sursa (job #434642) | Cod sursa (job #544611) | Cod sursa (job #600625)
Cod sursa(job #600625)
# include <cstdio>
# include <cstring>
const char *FIN = "strmatch.in", *FOU = "strmatch.out";
const int MAX = 2000005;
char needle[MAX], haystack[MAX];
int S[1005];
int bmGs[MAX], bmBc[MAX], suff[MAX];
void preBmBc(char *x, int m, int bmBc[]) {
int i;
for (i = 0; i < MAX; ++i)
bmBc[i] = m;
for (i = 0; i < m - 1; ++i)
bmBc[x[i]] = m - i - 1;
}
void suffixes(char *x, int m, int *suff) {
int f, g, i;
suff[m - 1] = m;
g = m - 1;
for (i = m - 2; i >= 0; --i) {
if (i > g && suff[i + m - 1 - f] < i - g)
suff[i] = suff[i + m - 1 - f];
else {
if (i < g)
g = i;
f = i;
while (g >= 0 && x[g] == x[g + m - 1 - f])
--g;
suff[i] = f - g;
}
}
}
void preBmGs(char *x, int m, int bmGs[]) {
int i, j;
suffixes(x, m, suff);
for (i = 0; i < m; ++i)
bmGs[i] = m;
j = 0;
for (i = m - 1; i >= 0; --i)
if (suff[i] == i + 1)
for (; j < m - 1 - i; ++j)
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
for (i = 0; i <= m - 2; ++i)
bmGs[m - 1 - suff[i]] = m - 1 - i;
}
inline int max (int a, int b) {
return a > b ? a : b;
}
void BM(char *x, int m, char *y, int n) {
int i, j;
/* Preprocessing */
preBmGs(x, m, bmGs);
preBmBc(x, m, bmBc);
/* Searching */
j = 0;
while (j <= n - m) {
for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
if (i < 0) {
++S[0];
if (S[0] < 1001) S[S[0]] = j;//OUTPUT(j);
j += bmGs[0];
}
else
j += max(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
}
int main (void) {
freopen (FIN, "r", stdin);
scanf ("%s %s", needle, haystack);
BM (needle, strlen(needle), haystack, strlen(haystack));
freopen (FOU, "w", stdout);
printf ("%d\n", S[0]);
for (int i = 1; i <= S[0] && i <= 1000; ++i)
printf ("%d ", S[i]);
}