k-string

给一个长度为n的字符串S,定义k-string为在字符串S中出现次数大于等于k次的子串,也就是存在至少k对(i,j)使得0 <= i <= j < n且Si,Si+1…Sj构成的子串与该k-string相同。现给一个初始字符串,然后执行m个操作,每个操作有两种:1.往当前字符串S末尾添加一个字符; 2.询问当前不同的k-string有多少种。

这题可以用sa的h数组做 也可以用构后缀树做
先说下sa的(我没写 只是随便写个思路=-=
【sa】
先把字符串倒过来 这样每次插入就等于插入一个后缀
给每个后缀一个编号 代表插入时询问到第几个询问了
h数组可以画成像这样的柱状图(左)
1
然后可以把它从上到下划分成好几个矩形(右)
划分可以排序+链表做

然后对于一个矩形 记录3个信息 l r h
对于这个矩形的贡献就是:l~r这些后缀中 第k个出现的时间
在这个时间后的询问 这个矩形都能对其贡献h的答案
可以维护一个数组记录改变量 最后扫一遍就可以了

询问k大 题解上写的是用划分树 主席树应该也可以

【后缀树】
其实sam构的是前缀树 那刚好连字符串都不用倒过来了
同样一个插入代表是多了一个前缀
用上面同样的方法对前缀进行标号
考虑parent树上一个节点的贡献
一个节点能有贡献 当且仅当它出现了k次 即它有k个出现了的叶子
而他的贡献是t[now].l – t[t[now].f].l
同样维护一个改变量数组即可
这里的k大是在一个类似dfs序上询问的

有一个值得注意的地方 这题的空间限制是64(32)M
直接用sam+主席树会MLE
有两种办法 1是把sam的ch数组改成map
我试了试 TLE了=-=

还有就是 从下往上计算 对每个节点维护一个大根左偏树
对于一个儿子都计算过的节点 把所有儿子合并
然后不停删根 直到树的大小为k 这时根就是第k小的时间点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 100005;

struct node
{
    int ch[27], l, f;
}t[maxn * 2];

struct line
{
    int to, next;
}li[maxn * 4];

struct t_node
{
    int l, r, dis, v;
}tt[maxn];

int ans[maxn], is[maxn], tot, last, n, m, k, p, be[maxn * 2], l, tot_node, b[maxn * 2];
string s;

void makeline(int fr, int to)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
}

void add(char c, int len)
{
    c -= 'a';
    int now = ++tot, p = last;
    last = now;
    t[now].l = len;
    for (; p && !t[p].ch[c]; p = t[p].f) t[p].ch[c] = now;
    if (!p) t[now].f = 1;
    else
    if (t[p].l + 1 == t[t[p].ch[c]].l) t[now].f = t[p].ch[c];
    else
    {
        int r = ++tot, ch = t[p].ch[c];
        t[r] = t[ch];
        t[r].l = t[p].l + 1;
        t[ch].f = t[now].f = r;
        for (; p && t[p].ch[c] == ch; p = t[p].f) t[p].ch[c] = r;
    }
}

int merge(int a, int b)
{
    if (!a) return b;
    if (!b) return a;
    if (tt[a].v < tt[b].v) swap(a, b);
    tt[a].r = merge(tt[a].r, b);
    if (tt[tt[a].l].dis < tt[tt[a].r].dis) swap(tt[a].l, tt[a].r);
    tt[a].dis = tt[tt[a].r].dis + 1;
    return a;
}

pair<int, int> dfs(int now)
{
    int root = 0, sum = 0;
    if (!b[now] && t[now].l != 1)
    {
        ++tot_node;
        tt[tot_node].l = tt[tot_node].r = 0;
        tt[tot_node].dis = 1;
        tt[tot_node].v = is[t[now].l - 1];
        root = tot_node;
        sum = 1;
    }
    for (int i = be[now]; i; i = li[i].next)
    {
        pair<int, int> t = dfs(li[i].to);
        root = merge(root, t.first);
        sum += t.second;
    }
    if (now == 1 || sum < k) return make_pair(root, sum);
    while (sum > k) root = merge(tt[root].l, tt[root].r), --sum;
    ans[tt[root].v] += t[now].l - t[t[now].f].l - (!b[now] ? 1 : 0);
    return make_pair(root, sum);
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &k);
    cin >> s;
    s = '{' + s;
    tot = last = 1;
    for (int i = 0; i < s.length(); ++i)
        add(s[i], i + 1), is[i] = 0;
    for (int i = 0; i < m; ++i)
    {
        int t;
        scanf("%d", &t);
        if (t == 1)
        {
            char tc, c;
            scanf("%c%c", &tc, &c);
            is[s.length()] = p;
            s += c;
            add(c, s.length());
        }
        else ++p;
    }
    for (int i = 1; i <= tot; ++i)
        makeline(t[i].f, i), b[t[i].f] = 1;
    tot_node = 1;
    dfs(1);
    int as = 0;
    for (int i = 0; i < p; ++i)
    {
        as += ans[i];
        printf("%d\n", as);
    }
    fclose(stdin);fclose(stdout);
}

BZOJ 2342: [Shoi]双倍回文

这题我开始的时候是吧字符串反接在原串后面
中间加分隔
然后二分“半串”的长度
在一块中找出在这块中有回文的中心
然后按半径排下序
然后用线段树维护哪些点有中心
但是这样的复杂度是O(nlog^2n)的!
交上去就T了 QAQ

so我就去找正解了,,
正解是处理出所有回文的中心 和半径后
按中心排序
另外用一个数组记录按回文左边界排序
对于一个中心 把左边界小于它的回文的中心加入一个set
每次找到<=(当前中心 + 当前右边界)/2的最大的中心
用他们去更新ans
————code—————

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 1100000;
struct point
{
  int o, l, r;
  point(int a = 0, int b = 0) : o(a), l(b) { r = 2 * o – l + 1; }
}p[maxn], p2[maxn];
int sa_t[maxn], as[maxn], sa[maxn], v[maxn], v_t[maxn], t[maxn], cnt[maxn], rank[maxn], h[maxn], n, tt[maxn * 5], t2[maxn * 2];
string s;
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; m = p, j <<= 1)
  {
    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 = p = 1, v[sa[0]] = 0; i < n; ++i)
      v[sa[i]] = same(sa[i], sa[i – 1], j) ? p – 1 : p++;
  }
}
void get_h(int n)
{
  for (int i = 0; i < n; ++i) rank[sa[i]] = i;
  for (int i = 0, k = 0; i < n; h[rank[i++]] = k)
  if (rank[i])
    for (k = k ? k – 1 : 0; s[i + k] == s[sa[rank[i] – 1] + k]; ++k);
  else k = 0;
}
void build(int now, int l, int r)
{
  if (l == r)
  {
    tt[now] = h[l];
    return;
  }
  int mid = (l + r) / 2;
  build(now * 2, l, mid);
  build(now * 2 + 1, mid + 1, r);
  tt[now] = min(tt[now * 2], tt[now * 2 + 1]);
}
int query(int now, int l, int r, int lf, int rt)
{
  if (l >= lf && r <= rt) return tt[now];
  int mid = (l + r) / 2, ans = 0x7fffffff;
  if (lf <= mid) ans = min(ans, query(now * 2, l, mid, lf, rt));
  if (rt >= mid + 1) ans = min(ans, query(now * 2 + 1, mid + 1, r, lf, rt));
  return ans;
}
int get(int l, int r)
{
  if (l > r) swap(l, r);
  return query(1, 0, s.length() – 1, l + 1, r);
}
set<int> f;
set<int>::iterator it;
bool cmp1(point a, point b) { return a.o < b.o; }
bool cmp2(point a, point b) { return a.l < b.l; }
int main()
{
  cin >> n >> s;
  s += ‘&’;
  for (int i = n – 1; i >= 0; –i) s += s[i];
  s += (char)1;
  get_sa(s.length(), 300);
  get_h(s.length());
  memset(t, 0, sizeof(t));
  build(1, 0, s.length() – 1);
  int m = 0;
  for (int i = 0; i < n; ++i)
  if (int k = get(rank[i], rank[s.length() – i – 1]))
    p2[m] = p[m] = point(i – 1, i – k), ++m;
  sort(p, p + m, cmp1);
  sort(p2, p2 + m, cmp2);
  int j = 0, ans = 0;
  for (int i = 0; i < m; ++i)
  {
    while (j < m && p2[j].l <= p[i].o + 1) f.insert(p2[j++].o);
    it = f.upper_bound((p[i].o + p[i].r) / 2);
    it–;
    ans = max(ans, ((*it) – p[i].o) * 4);
  }
  cout << ans;

}

BZOJ 2754: [SCOI2012]喵星球上的点名

这题我是用了yy大神的方法——

yangyue1995 @ 2012-06-01 23:53:48

Quote ] [ Edit ] [ Delete ] 2#
这题暴力SA + 对height上下扫可过…

把所有字符串连接起来
中间用不一样的符号隔开
求完h后
对一个点名串开头位置为首的后缀往前往后扫 直到遇到 <len[i]的h
各种乱搞即可
这样会略慢啊
然后貌似AC自动机的话也不能保证复杂度。。
然后就没有然后了。。
好吧、 然后求正解。。@杨越
———–code————

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 310005;
int s[maxn], v[maxn], sa[maxn], t[maxn], rank[maxn], h[maxn], n, m, k,
    p[maxn], l[maxn], pt[maxn], b[maxn], to[maxn], ans[maxn];
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 i = 0; i < n; ++i) v[i] = s[i];
  for (int j = 0, p = 1, i; p < n; k = j = j ? (j << 1) : 1)
  {
    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++;
  }
}
void get_h(int n)
{
  for (int i = 0; i < n; ++i) rank[sa[i]] = i;
  for (int i = 0, k = 0; i < n; h[rank[i++]] = k)
  if (rank[i])
    for (k = k ? k – 1 : 0; s[i + k] == s[sa[rank[i] – 1] + k]; ++k);
  else k = 0;
}
int add(int k, int now)
{
  int t = pt[sa[k]];
  if (t == -1 || b[t] == now) return 0;
  b[t] = now;
  ++ans[t];
  return 1;
}
int main()
{
  scanf(“%d%d”, &n, &m);
  int num = 1000000;
  int len = 0;
  for (int i = 0; i < n; ++i)
    for (int z = 0; z < 2; ++z)
    {
      int k;
      scanf(“%d”, &k);
      for (int j = 0; j < k; ++j)
      {
        scanf(“%d”, &s[len]);
        pt[len++] = i;
      }
      s[len] = num++;
      pt[len++] = -1;
    }
  for (int i = 0; i < m; ++i)
  {
    int k;
    scanf(“%d”, &k);
    l[i] = k;
    to[i] = len;
    for (int j = 0; j < k; ++j)
    {
      scanf(“%d”, &s[len]);
      pt[len++] = -1;
    }
    s[len] = num++;
    pt[len++] = -1;
  }
  s[len] = -1;
  pt[len++] = -1;
  for (int i = 0; i < len; ++i) t[i] = s[i];
  sort(t, t + len);
  int q = unique(t, t + len) – t;
  for (int i = 0; i < len; ++i) s[i] = lower_bound(t, t + q, s[i]) – t;
  get_sa(len);
  get_h(len);
  for (int i = 0; i <= n; ++i) b[i] = -1;
  for (int i = 0; i < m; ++i)
  {
    int as = 0;
    for (int j = rank[to[i]]; j >= 0; –j)
    {
      as += add(j, i);
      if (h[j] < l[i]) break;
    }
    for (int j = rank[to[i]] + 1; j < len; ++j)
    {
      if (h[j] < l[i]) break;
      as += add(j, i);
    }
    printf(“%d\n”, as);
  }
  for (int i = 0; i < n – 1; ++i) printf(“%d “, ans[i]);
  printf(“%d”, ans[n – 1]);
}

后缀数组小结②

【cxjyxx_me是个大沙茶 他连后缀数组这个pj算法都不会。。】
h[i]      表示sa[i]和sa[i – 1]的最长公共前缀

O(n^2)的朴素就很傻×了
但是按lsq的话说  这 样 做 并 没 有 利 用 字 符 串 的 性 质 。
可以证明(论文里。。)
h[i] >= h[i – 1] – 1
所以只要按0~n-1的顺序求h值就可以达到O(n)的时间出解
void get_h(int n)
{
  for (int i = 0; i < n; ++i) rank[sa[i]] = i;
  for (int i = 0, k = 0; i < n; h[rank[i++]] = k)
  if (rank[i])
    for (k = k ? k – 1 : 0; s[i + k] == s[sa[rank[i] – 1] + k]; ++k);
  else k = 0;
}

h[i]      表示sa[i]和sa[i – 1]的最长公共前缀
rank[i] 表示第i个后缀的rank值
这个代码貌似就没什么好解释的了了。。
就是比lsq的代码多判了一个rank
因为的的sa下标是从0开始、
————————————
另附一个预处理方法
o(nlogn)的预处理 可以在O(1)查询任意两个后缀的最长公共前缀
dp[i][j]  表示从h[i]开始的1<<j个h值的min
这个可以nlogn求出来

然后要求h[l]~h[r]的最小值时
设k为floor(log_2(r – l))
最小值为min(dp[l][k], dp[r – (1 << k)][k])
这只是思路 具体下标好像有点不一样、、
———————应用———————-
这些基本就是概述下论文里的应用了。。

最长公共前缀
min(h[rank[l]+1]~h[rank[r]])
可重叠最长重复子串
h数组max值
不可重叠最长重复子串
二分长度 可以用mid把h数组分成好几块
如果在一块中出现两个坐标绝对值>=mid则返回true
可重叠的最长重复k次子串
     二分长度 分块后如果有一块元素个数>=k个则返回true
不相同的子串的个数
按rank值从小到大循环后缀
考虑一个后缀对不同子串的贡献是len-h[i]
最长回文子串
把s翻转后接接在s串后面 中间要加一个没出现过的字符作为分隔
考虑以第i个字符为中心的回文串长度即为后缀i和后缀len-i的最长公共前缀
奇数偶数都要考虑
奇偶使用的后缀是不一样的
连续重复子串
枚举长度为i 考虑后缀0和后缀i的最长公共前缀 可以在预处理后O(1)判断是否合法
重复次数最多的连续重复子串
枚举这个子串的长度为L
那么这个子串必定包含0, L*1, L* 2, …, L*m
枚举这几个位置
求出 L * i 和 L*(i + 1)  的最长公共前缀和最长公共后缀
设长度为k 则重复了k/L+1次 更新ans

2串最长公共子串
把第二个串接到第一个串后面 并在中间加入一个没出现的分隔符
求出sa和h后
枚举第一个串的每一位
如果sa[rank[i] + 1]是第二个串的后缀 则可以用h[rank[i + 1]]更新答案
如果sa[rank[i] – 1]是第二个串的后缀 则可以用h[rank[i ]]更新答案

长度不小于 k 的公共子串的个数
这个也是用h数组乱搞一下就行了 由于我对这题的定义不是很理解 就不写了。。
不小于 k 个字符串中的最长子串
对于多字符串问题 一般的处理方法是把所有字符串连接起来并每两个间用不一样的字符隔开
二分长度 对h分块 如果一块中出现k个字符串则返回true
每个字符串至少出现两次且不重叠的最长子串
二分长度 如果一块对每个字符串都出现了坐标绝对值>=mid的两个后缀 则返回true

出现或反转后出现在每个字符串中的最长子串
二分长度 如果一块对每个字符串都出现了后缀或反转后的后缀 则返回true
————————————————
终于写完了=、=。。 还有写的一些题目 放在后几篇吧- -‘

后缀数组小结①

【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数组的求法和后缀数组的一些应用扔到下一篇写吧。。