Advertisement
Guest User

Untitled

a guest
Nov 1st, 2012
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.03 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement