Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Nov 1st, 2012  |  syntax: C++  |  size: 2.03 KB  |  views: 10  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. typedef unsigned long long ULL;
  2.  
  3. const ULL BASE = 1E9 + 7;
  4.  
  5. const int MAXN = 105, MAXM = 100055;
  6.  
  7. int N, M;
  8.  
  9. ULL hashfront[MAXN][MAXM];
  10. ULL hashback[MAXN][MAXM];
  11. ULL prec[MAXM];
  12.  
  13. ULL fhash(int i, int start, int len)
  14. {
  15.         return (hashfront[i][start + len] - hashfront[i][start]) * prec[start];
  16. }
  17.  
  18. //start references a position in the fwd string
  19. ULL bhash(int i, int start, int len)
  20. {
  21.         int end = M - start;
  22.         int sstart = end - len;
  23.         return (hashback[i][end] - hashback[i][sstart]) * prec[sstart];
  24. }
  25.  
  26. int match(int a, int b)
  27. {
  28.         int lo = 0, hi = M;
  29.         while (lo < hi)
  30.         {
  31.                 int mid = 2;((hi + lo) / 2) + 1;
  32.                 printf("lo=%d hi=%d mid=%d\n", lo, hi, mid);
  33.                 printf("fhash=%llu bhash=%llu\n", fhash(a, 0, mid), bhash(b, M-1, mid));
  34.                 if (fhash(a, 0, mid) == bhash(b, M-1, mid))
  35.                 {
  36.                         printf("match\n");
  37.                         lo = mid;
  38.                 }
  39.                 else
  40.                 {
  41.                         printf("Nope\n");
  42.                         hi = mid;
  43.                 }
  44.                 getchar();
  45.         }
  46.         return lo;
  47. }
  48.  
  49. //front of a, back of B
  50. int find(int a, int b)
  51. {
  52.         int cur = match(a, b);
  53.  
  54.         //find longest
  55.  
  56.         return cur;
  57. }
  58.  
  59. char buf[MAXM];
  60.  
  61. int main(int argc,char *argv[]) {
  62.         if (argc>1) fout=stdout;
  63.         prec[0] = 1;
  64.         for (int i = 1; i <= MAXM; i++)
  65.                 prec[i] = prec[i-1] * BASE;
  66.         fscanf(fin, "%d %d", &N, &M);
  67.         for (int i = 0; i < N; i++)
  68.         {
  69.                 scanf("%s", &buf);
  70.                 for (int j = 0; j < M; j++)
  71.                 {
  72.                         // hashfront[i][j + 1] = hashfront[i][j] * BASE + buf[j];
  73.                         hashfront[i][j + 1] = hashfront[i][j] + (prec[M - j - 1] * (ULL)buf[j]);
  74.                 }
  75.                 for (int j = 0; j < M; j++)
  76.                 {
  77.                         // hashback[i][j + 1] = hashback[i][j] * BASE + buf[M - 1 - j];
  78.                         hashback[i][j + 1] = hashback[i][j] + (prec[M - j - 1] * (ULL)buf[M - 1 - j]);
  79.                 }
  80.                 printf("str=%s\n", buf);
  81.                 for (int j = 1; j <= M; j++)
  82.                         printf("j=%d fhash=%llu bhash=%llu\n", j, hashfront[i][j], hashback[i][j]);
  83.         }
  84.         //printf("match = %d\n", match(0, 2));
  85.         // int ans = -1;
  86.         // for (int i = 0; i < N; i++)
  87.         // {
  88.         //      for (int j = 0; j < N; j++)
  89.         //      {
  90.         //              if (i == j) continue;
  91.         //              ans = max(find(i, j), ans);
  92.         //      }
  93.         // }
  94.         // printf("%d\n", ans);
  95.         return 0;
  96. }