SAM-模板和学习

先上一道裸题代码：给定若干个(<=10)由小写字母组成的字符串(每个字符串长度不超过10^5)，求他们的最长公共子串的长度。

用的是在每个字符串中间加间隔符，把它们合成一个字符串，最后 DFS + 标记找答案的方法。

 1 #include <stdio.h>
 2 #include <unordered_map>
 3 #include <string.h>
 4 #include <vector>
 5 
 6 using namespace std;
 7 
 8 const int _N = 100005;
 9 
10 char str[_N];
11 vector<int> G[_N*20];
12 
13 namespace SAM {
14     int root, tot, last, lcs, par[_N*20], mx[_N*20], mk[_N*20];
15     unordered_map<int, int> son[_N*20];
16     
17     int Ins(int v_mx, int v_mk) { mx[++tot] = v_mx; mk[tot] = v_mk; return tot; }
18     
19     void Init() { tot = 0; root = last = Ins(0, 0); return; }
20     
21     void dfs(int node, int FULL)
22     {
23         for (int i = G[node].size()-1; i >= 0; --i)
24             dfs(G[node][i], FULL), mk[node] |= mk[G[node][i]];
25         if (mk[node] == FULL && lcs < mx[node])
26             lcs = mx[node];
27     }
28     
29     void GetLCS(int FULL)
30     {
31         int lcs = 0, i;
32         for (i = 1; i <= tot; ++i)
33             G[par[i]].push_back(i);
34         lcs = 0;
35         dfs(root, FULL);
36         return;
37     }
38     
39     void Extend(int t, int id)
40     {
41         int np, nq, p, q;
42         np = Ins(mx[last] + 1, id);//---
43         for (p = last; p && !son[p][t]; p = par[p])
44             son[p][t] = np;
45         if (!p) {
46             par[np] = root;
47         } else {
48             q = son[p][t];
49             if (mx[q] == mx[p] + 1) {
50                 par[np] = q;
51             } else {
52                 nq = Ins(mx[p] + 1, mk[q]);//---
53                 son[nq] = son[q];
54                 par[nq] = par[q], par[q] = par[np] = nq;
55                 for ( ; p && son[p][t] == q; p = par[p])
56                     son[p][t] = nq;
57             }
58         }
59         last = np;
60         return;
61     }
62     
63 }
64 
65 int main()
66 {
67     int i, cnt = 1, len;
68     scanf("%s", str);
69     SAM::Init();
70     len = strlen(str);
71     for (i = 0; i < len; ++i)
72         SAM::Extend(str[i]-'a', cnt);
73     while (scanf("%s", str) != -1) {
74         len = strlen(str);
75         cnt <<= 1;
76         SAM::Extend(26, cnt);
77         for (i = 0; i < len; ++i)
78             SAM::Extend(str[i]-'a', cnt);
79     }
80     SAM::GetLCS((cnt<<1)-1);
81     printf("%d
", SAM::lcs);
82     return 0;
83 }

其实现在也不太会 SAM OrzOrzOrz，好像给自己埋了一个坑， SAM 相关的训练也已经结束了，只能以后慢慢填啦。

这两个月打了不少比赛，没写题解，等放假补吧OrzOrz...