Cod sursa(job #600625)

Utilizator cont_de_testeCont Teste cont_de_teste Data 2 iulie 2011 17:33:06
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
# 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]);
}