Cod sursa(job #1852210)

Utilizator lorundlorund lorund Data 20 ianuarie 2017 16:55:37
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#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;
}