codevs3160 最长公共子串

传送门：http://codevs.cn/problem/3160/

【题解】

CTSC前复习模板

sa的模板。。记住基数排序就够了（还有height）

还有就是sa[i]表示排名为i的后缀是啥。。rnk[i]表示suf(i)排第几

至于其他。。看造化了

大多数关于两个串的都要把它们接起来，然后上SA。

（两个串瞎jb匹配明明还可以FFT嘛）

那么这题。。按套路就是这么走的

可是怎么计算贡献呢

我们发现这样一个事情：

如果suf(sa[i]),suf(sa[j])有公共部分，那么一定不比suf(sa[i],suf(sa[j+1])劣。

我们按照后缀排序后，如果sa[i],sa[i+1]一个处于前半（s1），一个处于后半（s2），那么就是一个合法的匹配，更新答案。

另：还是不会SAM

# include <stdio.h>
# include <string.h>
# include <algorithm>
// # include <bits/stdc++.h>using namespace std;typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 2e5 + 10;
const int mod = 1e9+7;# define RG register
# define ST staticchar s1[M], s2[M]; 
char str[M]; 
int n, len1, len2; namespace SA {// rnk[i]: i后缀排名多少；sa[i]: 排名为i的后缀是哪个 int rnk[M], sa[M], h[M], tsa[M], A[M], B[M];int cntA[M], cntB[M]; inline void set() {memset(cntA, 0, sizeof cntA); for (int i=1; i<=n; ++i) ++cntA[str[i]]; for (int i=1; i<=255; ++i) cntA[i] += cntA[i-1];for (int i=n; i; --i) sa[cntA[str[i]] --] = i;rnk[sa[1]] = 1; for (int i=2; i<=n; ++i) { rnk[sa[i]] = rnk[sa[i-1]];if(str[sa[i]] != str[sa[i-1]]) ++rnk[sa[i]]; }for (int len=1; rnk[sa[n]] < n; len<<=1) {memset(cntA, 0, sizeof cntA);memset(cntB, 0, sizeof cntB); for (int i=1; i<=n; ++i) {cntA[A[i] = rnk[i]] ++;cntB[B[i] = ((i + len <= n) ? rnk[i+len] : 0)] ++;}for (int i=1; i<=n; ++i) cntA[i] += cntA[i-1], cntB[i] += cntB[i-1];for (int i=n; i; --i) tsa[cntB[B[i]] --] = i;for (int i=n; i; --i) sa[cntA[A[tsa[i]]] --] = tsa[i]; rnk[sa[1]] = 1; for (int i=2; i<=n; ++i) { rnk[sa[i]] = rnk[sa[i-1]];if(A[sa[i]] != A[sa[i-1]] || B[sa[i]] != B[sa[i-1]]) ++rnk[sa[i]]; }        }for (int i=1, j=0; i<=n; ++i) {if(j) --j;while(str[i+j] == str[sa[rnk[i]-1]+j]) ++j;h[rnk[i]] = j;}}
}int main() {scanf("%s", s1); len1 = strlen(s1); for (int i=0; i<len1; ++i) str[++n] = s1[i];str[++n] = 233;scanf("%s", s2);len2 = strlen(s2);for (int i=0; i<len2; ++i) str[++n] = s2[i]; SA::set(); int bet = len1 + 1, ans = 0;for (int i=1; i<n; ++i) {if((SA::sa[i] < bet && SA::sa[i+1] > bet) || (SA::sa[i] > bet && SA::sa[i+1] < bet))ans = max(ans, SA::h[i+1]);}printf("%d\n", ans); return 0;
}