Pagini recente » Cod sursa (job #759447) | Cod sursa (job #3205907) | Cod sursa (job #2705407) | Cod sursa (job #1795696) | Cod sursa (job #1852210)
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define OUTPUT(x) cout << x << " "
#define ASIZE 0x100
int solCnt;
int pos[1005], lps[2000005];
char pat[2000005], txt[2000005];
void preBmBc(char *x, int m, int bmBc[]) {
int i;
for (i = 0; i < ASIZE; ++i)
bmBc[i] = m;
for (i = 0; i < m - 1; ++i)
bmBc[x[i]] = m - i - 1;
}
void TUNEDBM(char *x, int m, char *y, int n) {
int j, k, shift, bmBc[ASIZE];
/* Preprocessing */
preBmBc(x, m, bmBc);
shift = bmBc[x[m - 1]];
bmBc[x[m - 1]] = 0;
memset(y + n, x[m - 1], m);
/* Searching */
j = 0;
while (j < n) {
k = bmBc[y[j + m -1]];
while (k != 0) {
j += k; k = bmBc[y[j + m -1]];
j += k; k = bmBc[y[j + m -1]];
j += k; k = bmBc[y[j + m -1]];
}
if (memcmp(x, y + j, m - 1) == 0 && j < n) {
++solCnt;
if (solCnt<=1000) pos[solCnt] = j;
}
j += shift; /* shift */
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", pat);
scanf("%s", txt);
TUNEDBM(pat, strlen(pat), txt, strlen(txt));
printf("%d\n", solCnt-1);
for (int i = 1; i <= min(solCnt-1, 1000); ++i)
printf("%d ", pos[i]);
return 0;
}