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 2806: [CTSC2012 Day2 T1]熟悉的文章(cheat)

传说中ctsc fhq为clj出的题。。
直接把作文库的串连接起来
中间用2隔开
然后对于一个待考察的作文
找到每一位最多能匹配到哪一位
然后二分答案
用一个队列维护决策
因为可以发现
如果决策j在i的时候被剔除了
那么在>=i的时候一定不会用到
然后在i时要先把i-mid这个状态加入队列
要维护单调性
然后就可以水过了
另外这题让我发现了sam比起sa倍增做法的一个弱点
如果字符种数极多
它不能很好的像sa那样毫无违和感的处理掉
应该要用hash或什么的。。会略蛋疼。。
——————-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 = 1200000;
struct node
{
  int f, ch[3], l;
}t[maxn * 2];
deque<int> v;
string s;
char c[maxn];
int n, m, l, la, k, a[maxn], f[maxn];
void add(int k, int len)
{
  int now = ++l; int p = la;
  la = now;
  t[now].l = len;
  for (; p && !t[p].ch[k]; p = t[p].f) t[p].ch[k] = now;
  if (!p) t[now].f = 1;
  else
    if (t[t[p].ch[k]].l == t[p].l + 1) t[now].f = t[p].ch[k];
    else
    {
      int c = t[p].ch[k], r = ++l;
      t[r] = t[c];
      t[r].l = t[p].l + 1;
      t[c].f = t[now].f = r;
      for (; p && t[p].ch[k] == c; p = t[p].f) t[p].ch[k] = r;
    }
}
void geta()
{
  for (int i = 0, now = 1, l = 0; i < s.length(); ++i)
  {
    while (now > 1 && !t[now].ch[s[i] – ‘0’]) now = t[now].f, l = t[now].l;
    if (t[now].ch[s[i] – ‘0’]) now = t[now].ch[s[i] – ‘0’], ++l;
    a[i + 1] = l;
  }
}
bool check(int mid)
{
  f[0] = 0;
  int len = s.length();
  while (!v.empty()) v.pop_back();
  for (int i = 1; i <= len; ++i)
  {
    if (i >= mid)
    {
      while(!v.empty() && f[v.back()] >= f[i – mid]) v.pop_back();
      v.push_back(i – mid);
    }
    while (!v.empty() && v.front() < i – a[i]) v.pop_front();
    f[i] = f[i – 1] + 1;
    if (!v.empty()) f[i] = min(f[i], f[v.front()]);
  }
  return s.length() >= f[len] * 10;
}
int getans()
{
  geta();
  int l = 0, r = s.length() + 1;
  while (l + 1 < r)
  {
    int mid = (l + r) / 2;
    if (check(mid)) l = mid;
    else r = mid;
  }
  return l;
}
int main()
{
  scanf(“%d%d”, &n, &m);
  for (int i = 0; i < m; ++i)
  {
    scanf(“\n%s”, c);
    string t = c;
    s += ‘2’, s += t;
  }
  la = l = 1;
  for (int i = 0; i < s.length(); ++i)
    add(s[i] – ‘0’, i + 1);
  for (int i = 0; i < n; ++i)
  {
    scanf(“\n%s”, c);
    s = c;
    printf(“%d\n”, getans());
  }

}

BZOJ 2555: SubString

给你一个字符串init,要求你支持两个操作

    (1):在当前字符串的后面插入一个字符串
    (2):询问字符串s在当前字符串中出现了几次?(作为连续子串)
    你必须在线支持这些操作。
—————————
在这题上我的一个很大的收益就是
发现就算不用交互式也可以强制在线。。。

这题是sam的挺基础的应用<为什么除了我只有5个人A?。。。。。。。>
求某节点代表串重复次数
唯一比较蛋疼的就是维护子树权值和要用动态树
或者用平衡树维护dfs序什么的、、
我是用动态树了、
写得十分的长= =
因为我的动态树长得十分的沙茶= =
【我不会说我这个题解是在等tc出成绩的时候写的- -】
——————-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 = 1300000;
struct point
{
  int ch[27], f, l;
}sa[maxn];
struct node
{
  int fa, l, r, v, lazy, c;
  bool root;
  node(int _fa = 0, int _l = 0, int _r = 0, int _v = 1, int _lazy = 0, int _c = 0, bool _root = true)
  : fa(_fa), l(_l), r(_r), v(_v), lazy(_lazy), c(_c), root(_root) {}
}t[maxn];
int mask, n, m, k, len, last, l, f[maxn];
char c[3000005];
string s;
string gets(string s, int mask)
{
  string chars = s;
  for (int j = 0; j < chars.length(); j++)
  {
    mask = (mask * 131 + j) % chars.length();
    char t = chars[j];
    chars[j] = chars[mask];
    chars[mask] = t;
  }
  return chars;
}
void down(int now)
{
  if (!now || !t[now].lazy) return;
  int k = t[now].lazy;
  t[now].lazy = 0;
  t[now].v += k;
  if (t[now].l) t[t[now].l].lazy += k;
  if (t[now].r) t[t[now].r].lazy += k;
}
void left(int now)
{
  int fa = t[now].fa;
  t[now].fa = t[fa].fa;
  if (t[t[fa].fa].l == fa) t[t[fa].fa].l = now;
  if (t[t[fa].fa].r == fa) t[t[fa].fa].r = now;
  t[fa].r = t[now].l;
  t[t[now].l].fa = fa;
  t[now].l = fa;
  t[fa].fa = now;
  t[now].root = t[fa].root;
  t[fa].root = false;
}
void right(int now)
{
  int fa = t[now].fa;
  t[now].fa = t[fa].fa;
  if (t[t[fa].fa].l == fa) t[t[fa].fa].l = now;
  if (t[t[fa].fa].r == fa) t[t[fa].fa].r = now;
  t[fa].l = t[now].r;
  t[t[now].r].fa = fa;
  t[now].r = fa;
  t[fa].fa = now;
  t[now].root = t[fa].root;
  t[fa].root = false;
}
void splay(int now)
{
  down(now);
  while (!t[now].root)
  {
    int fa = t[now].fa;
    if (t[fa].root)
    {
      down(fa), down(now);
      if (t[fa].l == now) right(now);
      else left(now);
    }
    else
    {
      int gfa = t[fa].fa;
      down(gfa), down(fa), down(now);
      if (t[gfa].l == fa)
        if (t[fa].l == now) right(fa), right(now);
        else left(now), right(now);
      else
        if (t[fa].l == now) right(now), left(now);
        else left(fa), left(now);
    }
  }
}
void cut_o(int now)
{
  if (!now) return;
  int fa = t[now].fa;
  if (!fa) return;
  if (t[fa].l == now) t[fa].l = 0;
  if (t[fa].r == now) t[fa].r = 0;
  t[now].root = true;
}
void access(int now)
{
  splay(now);
  while (t[now].fa)
  {
    int fa = t[now].fa;
    splay(fa);
    cut_o(t[fa].r);
    t[fa].r = now;
    t[now].root = false;
    splay(now);
  }
  cut_o(t[now].r);
}
void cut(int now)
{
  if (!now) return;
  int fa = f[now];
  if (!fa) return;
  int tans = 0;
  if (–t[fa].c == 0) ++tans;
  splay(now);
  tans += t[now].v;
  access(fa);
  t[fa].lazy -= tans;
  t[now].fa = 0;
}
void link(int now, int fa)
{
  int tans = 0;
  if (++t[fa].c == 1) tans -= 1;
  splay(now);
  tans += t[now].v;
  access(fa);
  t[fa].lazy += tans;
  t[now].fa = fa;
}
void setfa(int c, int _f)
{
  int t = sa[c].f;
  sa[c].f = _f;
  if (t) cut(c);
  link(c, _f);
  f[c] = _f;
}
void add(int k, int len)
{
  int now = ++l, p = last;
  last = now;
  sa[now].l = len;
  for (; p && !sa[p].ch[k]; p = sa[p].f) sa[p].ch[k] = now;
  if (!p) setfa(now, 1);
  else
    if (sa[sa[p].ch[k]].l == sa[p].l + 1) setfa(now, sa[p].ch[k]);
    else
    {
      int c = sa[p].ch[k], r = ++l;
      sa[r] = sa[c];
      sa[r].l = sa[p].l + 1;
      setfa(r, sa[r].f);
      setfa(c, r);
      setfa(now, r);
      for (; p && sa[p].ch[k] == c; p = sa[p].f) sa[p].ch[k] = r;
    }
}
int query()
{
  int n = s.length(), now = 1;
  for (int i = 0; i < n; ++i)
  {
    int t = s[i] – ‘A’;
    if (!sa[now].ch[t]) return 0;
    now = sa[now].ch[t];
  }
  splay(now);
  return t[now].v;
}
int main()
{
  scanf(“%d\n”, &n);
  scanf(“%s\n”, c);
  s = c;
  s = ((char)91) + s;
  l = last = 1;
  for (int i = 0; i < s.length(); ++i)
    add(s[i] – ‘A’, i + 1);
  len = s.length();
  for (int i = 0; i < n; ++i)
  {
    scanf(“%s\n”, c);
    s = c;
    if (s[0] == ‘A’)
    {
      scanf(“%s\n”, c);
      s = gets((string)c, mask);
      for (int i = 0; i < s.length(); ++i) add(s[i] – ‘A’, len + i + 1);
      len += s.length();
    }
    else
    {
      scanf(“%s\n”, c);
      s = gets((string)c, mask);
      int ans = query();
      mask ^= ans;
      printf(“%d\n”, ans);
    }
  }
}

后缀自动机小结②

【cxjyxx_me是个大沙茶 他连后缀自动机这个pj算法都不会。。】
后缀自动机的应用 我觉得最重要的是要知道这些性质:
①所有的子串都能由起始点走到
②加入前缀#后 在fail树上的叶子代表串各不相同 且共同组成串s的所有前缀
③从起始点走到所有”接受态点”的所有路径各不相同 且共同构成串s的所有后缀
[注:所谓接受态点 即last点及其所有祖先 即 last t[last].f t[t[last].f].f……..]

知道这几个性质感觉就所向披靡了~~
这里就讲一下clj课件里提到的题目吧<这些题我大多没写过。。只是讲下思路>
——————————–
最小循环串

给一个字符串S,每次可以将它的第一个字符移到最后面,求这样能得到的字典序最小的字符串。
——————————-
好吧这里的题目是直接copyCLJ的课件的。。所以字体有点奇葩、、 不要在意细节~~
这题其实是后缀数组的题啊= =
只要把s copy一个接在s的后面
求出最小的 起始点<=原s的length的后缀
这里顺便讲下怎么用sam线性构造sa吧
其实很简单 做一次dfs 对于一个节点 从它的ch[0]开始循环即可
然后如果到达一个接受态点即可吧当前串(可以用这个串的长度表示) 加入sa[]数组
因为按这样的循环方式进行dfs可以保证串的值是递增的 这个很显然
最后就可以得到sa数组了~
线性!
——————————-

SPOJ NSUBSTR
给一个字符串S,令F(x)表示S的所有长度为x的子串中,出现次数的最大值。求F(1)..F(Length(S))

——————————-
在fail树上 我们定义叶子节点的权值为1 其他节点权值为0
对于一个节点所代表串的出现次数就是以这个节点为根的子树权值和
为什么是这样呢?
我们知道每个叶子代表了一个前缀
且对于一个节点的代表串 一定是其子孙节点代表串的后缀
那么他的子孙中有几个是前缀就代表了这个节点的代表串出现了几次
然后对于每个节点i 用它的子树权值和去更新F(t[i].l)
最后再用每个F(i) 去更新F(i – 1)即可
为什么是对的?
这不是很显然么= =
一个长度是k的串出现了x次 那么它的长度为1~k的子串一定最少也可以出现x次- –
——————————-
BZOJ2555 SubString
——————————-
【因为这题是bzoj的 所以我有做(毫无节操- -)、后面的题解会写 这里就不写了】
——————————-
SPOJ SUBLEX
给一个长度不超过90000的串S,每次询问它的所有不同子串中,字典序第K小的,询问不超过500个。
———————————-
我们知道sam从起点开始走
可以走到所有子串
对于一个点i 它能走到的节点个数(一个节点以不同路径被走两次算两次)就代表了以它为前缀的子串个数
所以我们可以求出所有i的能走到的节点个数 记在num数组里
如果num[t[i].ch[0]] >= k那么就走到t[i].ch[0]否则k-= num[t[i].ch[0]] 然后循环下一个ch[1]
这个过程可以类比在平衡树上找k大
———————————-
还有两题LCS就不写了 【太难了不能直视(大雾】
END
然后等等放几题我刷的题的题解。。

后缀自动机小结①

【cxjyxx_me是个大沙茶 他连后缀自动机这个pj算法都不会。。】
后缀自动机。。
这个算法我看了<仅是看 没包括写> 近一个星期= =
肯定是我太沙茶了=、=
先推荐几篇文章吧,,

①显然是clj的论文                              《陈立杰营员交流资料.pptx》
②后缀自动机初窥                                http://blog.sina.com.cn/s/blog_7812e98601012cim.html
③后缀自动机与线性构造后缀树          http://fanhq666.blog.163.com/blog/static/8194342620123352232937/

④后缀自动机(FHQ+Neroysq补完)   http://hi.baidu.com/myidea/item/142c5cd45901a51820e25039
⑤后缀自动机的应用                            http://blog.sina.com.cn/s/blog_7812e98601012dfv.html

因为我太弱了、  用了一个星期的时间吧他们每个至少看了三遍才大概理解sam(Suffix Automaton)..<其实好像还是不是很理解。。>

先说下我对后缀自动机的理解吧。。(其实只是阐述一些性质。。)
如果说AC自动机可以识别所有前缀 那么 后缀自动机则可以识别所有子串!
也就是从s的sam的根开始走
走到每一个节点的路径形成的字符串各不相同
且构成了串s的所有子串!<=这个性质很科学有木有~

用fail指针构成的树就是一棵后缀树 (其实是前缀树。。但是用起来没什么差)

构造的时间复杂度根据势能分析是线性 (势能分析是什么? 我怎么知道。。。)

然后我们要做得就是构造一个满足这些性质的图。。。<恕我沙茶的理解。。>

先给一个串aabbab的sam图
psb (44)

(蓝边代表fail指针)
一个节点代表的字符串集为从s到这个点的所有路径集合
可以发现对于一个节点 他代表的串集在s上区间如下
[l, r]
[l + 1, r]
[l + 2, r]

[l + k, r]
如节点4 他代表的字符串集:
[1, 4] = aabb
[2, 4] = abb
[3, 4] = bb
这里定义min和max为l的取值区间
如 min[4] = 1, max[4] = 3
定义right为r
如right[4] = 4

介绍一下fail指针
对于fail[u]=v
有right[u] = right[v], max[u] + 1 = min[v]
可以类比kmp里的fail数组
就是fail[u]就是跟u的后面一坨一样的点
如fail[4]=5
5代表
[4, 4] = b

这样我们发现fail构出了一颗”前缀树”
和后缀树相同 为了使每个前缀都是叶子节点 我们不妨在串s前加入一个没出现的字符’#’
这里为了配合上面的图 就不加这个#了 下面给出串aabbab按fail构出的前缀树
psb (47)
(红色为路径上的值 蓝色为从根到这个点 经过的路径串拼起来 即为点的值 注意 这里的拼起来是往前加。。 看一下应该能理解)

如果加上#的话 就会有这样一个性质:每个叶子都不一样 且构出所有前缀
而#并不影响sam的构造

构造一个sam 我们要知道一个结构体:
struct node
{
int l, f, ch[26];
}t[maxn];

其中
l表示 这个点代表的字符串集里最长的长度
f表示 fail指针
至于ch数组 在fail树上不妨这样理解:
对于t[i].ch[j] 定义串k为i这个节点代表的最长串后面加入字符j所得的字符串
t[i].ch[j]是一个以k为后缀(严格包含  即len[k] <= t[t[i].ch[j]].l)的l值最小的节点
比如ch[ab]在aab和aaab中会选aab
看下这个图吧。。 有点乱。。。
psb (50)

sam的构造方法是逐个字符添加 也就是说你在添加第i个字符时 1~i-1个字符的sam已经建立了
现在考虑怎么在这个以建立的sam上添加一个字符
这里记录一个变量last 表示上次添加的节点是哪个 比如这个sam的last=7

现在考虑在这个sam上添加一个字符b 即新加入一个值为aabbabb的节点
他应该找到一个是他的后缀的节点作为他的父亲节点 然后插入进去
怎么找这个呢?
如果t[last].ch[‘b’]有节点 那么就是他了
不然就是
t[t[last].f].ch[‘b’]
t[t[t[last].f].f].ch[‘b’]
…..(即last的一堆祖先).ch[‘b’]
直到找到一个ch[‘b’]是有节点的。。
另外要把一路上的last, t[last].f, t[t[last].f].f…的ch[‘b’]都设为now (now为新节点编号)
如果一直到根 连根的ch[‘b’]都没有节点 那就直接把t[now].f设为根
否则对于一个节点p他有ch[‘b’] 设c=t[p].ch[‘b’] (如图p=8 c=4)
如果c是now的后缀 那就喜闻乐见直接把now的fail设为c就可以了
否则 可以知道的是c和now共享长度为t[p].l + 1的后缀
那么就新建一个节点r 表示这个被共享的后缀
再把now和c都弄成r的儿子即可~(即把t[now].f和t[c].f赋为r)
然后还要把所有p及祖先的ch[‘b’]==c的ch[‘b’]全部赋为r(满足l最小定理)
这样就完成了一次添加操作。。
然后把整个字符串一个个加进来就行了。。。
代码如下:
—————————————-

void add(int k, int len)
{
  int now = ++l, p = last;
  last = now;
t[now].l = len;
  for (; p && !t[p].ch[k]; p = t[p].f) t[p].ch[k] = now;   //找到ch[k]不为空的节点 且边把路上的节点的ch[k]赋为now
  if (!p) t[now].f = 1;
  else
    if (t[t[p].ch[k]].l == t[p].l + 1) t[now].f = t[p].ch[k];
    else
    {
      int c = t[p].ch[k], r = ++l;
      t[r] = t[c];
      t[r].l = t[p].l + 1;
      t[now].f = t[c].f = r;
      for (; p && t[p].ch[k] == c; p = t[p].f) t[p].ch[k] = r;   //可以证明对于某个节点到根的路径上的点的ch[k]值 一样的一定连续
    }

}
———————————————
好像比我的sa短了一行。。难道不是莫大的讽刺?=、=
终于写完了。。 写得好像有点略乱= =
题目、应用什么的明天再说吧。。 有点晚了- –