peltorator

Суффиксный массив

Dec 3rd, 2017
171
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const char C = 'a' - 1; // before first letter // change
  2. const char maxchar = 'z'; // change
  3.  
  4. vector<int> suffarray(string s) // without $ at the end
  5. {
  6.     vector<int> p, c, pn, cn, cnt;
  7.     int n = (int)s.size();
  8.     c.assign(n, 0);
  9.     for (int i = 0; i < n; i++)
  10.         c[i] = s[i] - C;
  11.     for (int j = 0; j <= (maxchar - C); j++)
  12.         for (int i = 0; i < n; i++)
  13.             if (c[i] == j)
  14.                 p.push_back(i);
  15.     int maxc = c[p.back()];
  16.     pn.resize(n);
  17.     for (int k = 0; (1 << k) <= 2 * n; k++)
  18.     {
  19.         for (int i = 0; i < n; i++)
  20.             pn[i] = ((p[i] -  (1 << k)) % n + n) % n;
  21.         cnt.assign(maxc + 3, 0);
  22.         for (int i = 0; i < n; i++)
  23.             cnt[c[i] + 1]++;
  24.         for (int i = 1; i <= maxc + 2; i++)
  25.             cnt[i] += cnt[i - 1];
  26.         for (int i = 0; i < n; i++)
  27.             p[cnt[c[pn[i]]]++] = pn[i];
  28.         cn.assign(n, 0);
  29.         cn[p[0]] = 1;
  30.         for (int i = 1; i < n; i++)
  31.             if (c[p[i]] == c[p[i - 1]] && c[(p[i] + (1 << k)) % n] == c[(p[i - 1] + (1 << k)) % n])
  32.                 cn[p[i]] = cn[p[i - 1]];
  33.             else
  34.                 cn[p[i]] = cn[p[i - 1]] + 1;
  35.         maxc = cn[p.back()];
  36.         c = cn;
  37.     }
  38.     return p;
  39. }
  40.  
  41. vector<int> findlcp(string s, vector<int> p)
  42. {
  43.     vector<int> lcp, mem;
  44.     int n = (int)s.size();
  45.     mem.resize(n);
  46.     for (int i = 0; i < n; i++)
  47.         mem[p[i]] = i;
  48.     lcp.assign(n, 0);
  49.     for (int i = 0; i < n; i++)
  50.     {
  51.         if (i)
  52.             lcp[mem[i]] = max(lcp[mem[i - 1]] - 1, 0);
  53.         if (mem[i] == n - 1)
  54.             continue;
  55.         while (max(i, p[mem[i] + 1]) + lcp[mem[i]] < n && s[i + lcp[mem[i]]] == s[p[mem[i] + 1] + lcp[mem[i]]])
  56.             lcp[mem[i]]++;
  57.     }
  58.     return lcp;
  59. }
RAW Paste Data