Chlience

【题解】SPOJ LCS Longest Common Substring
Probelm传送门 ＞ω＜题目大意：给定两个字符串 $s$ , $t$ ，求其最长公共子串的长度$1 \leq ... 扫描右侧二维码阅读全文 13 2018/10 # 【题解】SPOJ LCS Longest Common Substring ### Probelm 传送门 ＞ω＜ 题目大意： 给定两个字符串$s$,$t$，求其最长公共子串的长度$1 \leq lenth(a) , lenth(b) \leq 250000$### Solution 既然要求最长公共子串，能够保留所有子串信息的数据结构我们使用 SAM 考虑将串$s$建出 SAM ，然后用串$t$在 SAM 上进行匹配 如何匹配？ • 首先，设当前状态为$x$，匹配到了第$i$个字符$c$，匹配长度为$len$• 若$ch[x][c] \neq 0$，即有向$c$的转移，则$x = ch[x][c] , len = len + 1 , i = i + 1$• 若$ch[x][c] = 0$，即没有向$c$的转移 • 通过$fa$去找到能够转到$c$的最长后缀，即$x = fa[x]$，重复过程直到$ch[x][c] \neq 0$或者$x = 0$• 若$ch[x][c] \neq 0$那么状态进行转移，匹配长度$lenth = l[x] + 1$，状态$x = ch[x][c]$• 若$x = 0$则没有任何子串含有$c$。所以将长度$lenth = 0$，状态$x = 1$（也就是根） 同时，在匹配时维护一个匹配长度最大值即可 代码如下： #include <bits/stdc++.h> using namespace std; const int N = 300010; struct SAM { int ch[N << 1][26] , fa[N << 1]; int siz[N << 1] , l[N << 1]; int cnt , last , len; void ins(int c) { int x = last , nx = ++ cnt; last = nx; l[nx] = l[x] + 1; siz[nx] = 1; for(; x && !ch[x][c] ; x = fa[x]) ch[x][c] = nx; if(!x) fa[nx] = 1; else { int y = ch[x][c]; if(l[y] == l[x] + 1) fa[nx] = y; else { int ny = ++cnt; l[ny] = l[x] + 1; memcpy(ch[ny] , ch[y] , sizeof(ch[y])); fa[ny] = fa[y]; fa[y] = fa[nx] = ny; for(; ch[x][c] == y ; x = fa[x]) ch[x][c] = ny; } } } void insert(char *s) { len = strlen(s); last = cnt = 1; for(int i = 0 ; i < len ; ++ i) ins(s[i] - 'a'); } void work(char *s) { len = strlen(s); int x = 1 , lenth = 0 , ans = 0; for(int i = 0 ; i < len ; ++ i) { int c = s[i] - 'a'; if(ch[x][c]) {x = ch[x][c]; ++ lenth;} else { while(x && !ch[x][c]) x = fa[x]; if(x) {lenth = l[x] + 1; x = ch[x][c];} else {lenth = 0; x = 1;} } ans = max(ans , lenth); } printf("%d\n" , ans); } }sam; char s[N] , t[N]; int main() { scanf("%s %s" , s , t); sam.insert(s); sam.work(t); return 0; } Ps:不要问我为什么写 SAM 的时候之前用$slink$和$trans$然后这里又用$fa$和$ch\$

Last modification：October 13th, 2018 at 10:50 pm
If you think my article is useful to you, please feel free to appreciate