后缀数组小结①

【cxjyxx_me是个大沙茶 他连后缀数组这个pj算法都不会。。】
后缀数组其实就是一个用O(nlogn) 甚至O(n)(好像一般只用nlogn的)的时间求出一个字符串的所有后缀的排序顺序的算法
由于cxjyxx_me过于沙茶 以至于他直到3天前还不会这个算法。。<后缀数组推荐看lsq论文《后缀数组——处理字符串的有力工具》>
求出排序顺序后 还是不能很好的解决很多问题 所以又引入了h数组这个东西
h[i]表示第i名的后缀和第i-1名的后缀的最长公共前缀
可以用O(n)的时间求出 具体求法==再说、
先说nlogn求出排序顺序的方法吧,,
基本思想是倍增
对于第j次比较
以第i个字符开头的后缀只考虑s[i]s[i + 1]…s[i + (1 << j)]这个串
求出所有i的rank后
对于下一个++j
第i个字符开头的后缀的value就相当于是一个二元组(rank[i], rank[i +(1 << j – 1)])
在对每个i关于各自的二元组求出新的rank。。。
如果每次求rank是O(n)
显然整体复杂度最多O(nlogn)
那么怎么用O(n)求出每次的rank值呢?
其实要是只要求nlogn的方法就很显然了- – 直接双关键字排序就行了。。 这个程序后面会贴
O(n)的算法主要是用了基数排序
它先对第二关键字排序
然后就能保证在第一关键字相同时它们是按第二关键字排序的

怎么用基数排序做稳定排序呢?
记录基数数组cnt的前缀和
倒着循环 对于第i个数 可以知道第–cnt[v[i]]名是i
这样如果下次再出现v值跟这个v[i]一样的时候 他就会是前一名~

然后每次再把各自的rank作为新的value

先贴一个程序吧。
bool same(int a, int b, int j) { return t[a] == t[b] && t[a + j] == t[b + j]; }

void get_sa(int n, int m)
{
  for (int i = 0; i < n; ++i) ++cnt[v[i] = s[i]];
  for (int i = 1; i < m; ++i) cnt[i] += cnt[i – 1];
  for (int i = n – 1; i >= 0; –i) sa[–cnt[v[i]]] = i;
  for (int j = 1, p = 1, i; p < n; j <<= 1, m = p)
  {
    for (i = n – j, p = 0; i < n; ++i) sa_t[p++] = i;
    for (i = 0; i < n; ++i) if (sa[i] >= j) sa_t[p++] = sa[i] – j;
    for (i = 0; i < m; ++i) cnt[i] = 0;
    for (i = 0; i < n; ++i) ++cnt[v_t[i] = v[sa_t[i]]];
    for (i = 1; i < m; ++i) cnt[i] += cnt[i – 1];
    for (i = n – 1; i >= 0; –i) sa[–cnt[v_t[i]]] = sa_t[i], t[i] = v[i];
    for (i = 1, v[sa[0]] = 0, p = 1; i < n; ++i)
      v[sa[i]] = same(sa[i], sa[i – 1], j) ? p – 1 : p++;
  }
}

lsq的程序的一些地方太高端洋气了。。我就自己改了一点(我不会说我从来没写过指针、= =)
解释下数组

cnt 是基数数组
sa[i] 表示第i名是谁(这的是谁是指以第几个字符开头的后缀)
sa_t[i] 第二关键字第i名的是哪个
v[i] 就是value 也是上次的rank值
v_t[i] 表示第二关键字第i名的第一关键字的值
t 数组是存放v值 只用于same函数里面的比较

分段来解释吧

  for (int i = 0; i < n; ++i) ++cnt[v[i] = s[i]];
  for (int i = 1; i < m; ++i) cnt[i] += cnt[i – 1];
  for (int i = n – 1; i >= 0; –i) sa[–cnt[v[i]]] = i;
这个相当于求出j=0时的sa和v要预处理 (v值 即 rank值 可以离散 这没有影响)
———————————————————————————-
    for (i = n – j, p = 0; i < n; ++i) sa_t[p++] = i;

    for (i = 0; i < n; ++i) if (sa[i] >= j) sa_t[p++] = sa[i] – j;
求出第二关键字的sa值
可以发现n-j ~ n-1这几个后缀是没有第二关键字的 就当是0
然后按rank从小到大循环
如果一个后缀可以是某个后缀的第二关键字 就可以把那个后缀加入sa_t
———————————————————————————-

    for (i = 0; i < m; ++i) cnt[i] = 0;
    for (i = 0; i < n; ++i) ++cnt[v_t[i] = v[sa_t[i]]];
    for (i = 1; i < m; ++i) cnt[i] += cnt[i – 1];
    for (i = n – 1; i >= 0; –i) sa[–cnt[v_t[i]]] = sa_t[i], t[i] = v[i];
跟第一段差不多 就是要清空cnt数组
还有这句

for (i = n – 1; i >= 0; –i) sa[–cnt[v_t[i]]] = sa_t[i], t[i] = v[i];
可能比较难理解
其实就是按第二关键字从大到小循环加入sa
可以发现后循环到的后缀(即第二关键字比较小的后缀) 在第一关键字相同时会被放在前面
还有就是顺便把t数组赋了下值
———————————————————————————-

    for (i = 1, v[sa[0]] = 0, p = 1; i < n; ++i)
      v[sa[i]] = same(sa[i], sa[i – 1], j) ? p – 1 : p++;
求出新的v值长得比较不科学的就是那个三目操作符
其实就是判断下是不是有rank值相等的情况
———————————————————————————-
可以发现如果rank值都不一样就说明找出了ans 此时p会=n
否则也可以发现行的v数组的数值上限变为p
所以就有了外面这个循环:

for (int j = 1, p = 1, i; p < n; j <<= 1, m = p)
———————————————————————————-
看下直接用双关键字排序做得程序吧。。

bool cmp(int a, int b) { return v[a] < v[b] || (v[a] == v[b] && v[a + k] < v[b + k]); }
bool same(int a, int b, int j) { return t[a] == t[b] && t[a + j] == t[b + j]; }
void get_sa(int n)
{
  for (int j = 0, p = 1, i; p < n; j = !j ? 1 : (j << 1),k = j)
  {
    for (i = 0; i < n; ++i) sa[i] = i, t[i] = v[i];
    sort(sa, sa + n, cmp);
    for (i = p = 1, v[sa[0]] = 0; i < n; ++i)
      v[sa[i]] = same(sa[i], sa[i – 1], j) ? p – 1 : p++;
  }
}

是不是有种呵呵的感觉?~
那就呵呵吧、
这个的复杂度是O(n*log(n)^2 )
我不会说我昨天晚上写一题写到12点
最后发现t了 TAT
然后发现他的范围是50w,,,
就改成nlogn的算法。。
9.3s险过。。
———————————————————————————-
然后h数组的求法和后缀数组的一些应用扔到下一篇写吧。。

后缀数组小结①》上有2条评论

发表评论