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\n", SAM::lcs); 82 return 0; 83 }

 

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

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

转载于:https://www.cnblogs.com/ghcred/p/9167731.html

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的SAM-模板和学习的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。