POJ 2217

题目大意是给定两个字符串，求两个字符串的最长公共子串。 网上大部分给的都是LCP啊..? 我的第一想法就是二分子串的长度，开始想用哈希搞一搞，后来发现还是还是后缀数组扎实。 所以二分子串长度，当找到一个长度可以使一个字符串s1中的子串在字符串s2中出现，长度++，保存答案，否则-- 然后后缀数组来查询就好了。 #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int maxn = 10000 + 10; int lenB, lenA; int t[maxn], t2[maxn], sa[maxn], c[maxn]; char B[maxn], A[maxn]; int mp[maxn], m, n; void SA(){ n = lenB; int *x = t, *y = t2; for(int i = 0; i < m; ++i) c[i] = 0; for(int i = 0; i < n; ++i) c[x[i] = mp[(int)B[i]]]++; for(int i = 1; i < m; ++i) c[i] += c[i - 1]; for(int i = n - 1; i >= 0; --i) sa[--c[x[i]]] = i; for(int k = 1; k <= n; k<<=1) { int p = 0; for(int i = n - k; i < n; ++i) y[p++] = i; for(int i = 0; i < n; ++i) if(sa[i] >= k) y[p++] = sa[i] - k; for(int i = 0; i < m; ++i) c[i] = 0; for(int i = 0; i < n; ++i) c[x[y[i]]]++; for(int i = 1; i < m; ++i) c[i] += c[i - 1]; for(int i = n - 1; i >= 0; --i) sa[--c[x[y[i]]]] = y[i]; swap(x, y); p = 1; x[sa[0]] = 0; for(int i = 1; i < n; ++i) { x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p - 1:p++; } if(p >= n) break; m = p; } } int lenm; int cmp(char *pattern, int pos){ return strncmp(pattern, B + sa[pos], lenm); } int find(char *p, int tmp) { lenm = tmp; if(cmp(p, 0) < 0) return -1; if(cmp(p, n - 1) > 0) return -1; // printf("fuck\n"); int L = 0, R = n - 1; while(R >= L) { int M = L + (R - L) / 2; int res = cmp(p, M); if(!res) return M; if(res < 0) R = M - 1; else L = M + 1; } return -1; } bool can(int tmp){ for(int i = 0; i + tmp <= lenA; ++i) { if(find(A + i, tmp) != -1) { return true; } } return false; } void solve(){ int x = 1, y = lenA; int ans = 0; while(x <= y){ int M = x + (y - x) / 2; if(can(M)) { ans = M; x = M + 1; }else{ y = M - 1; } } printf("Nejdelsi spolecny retezec ma delku %d.\n", ans); } void init(){ memset(mp, -1, sizeof(mp)); vector<int> vs; m = 0; for(int i = 0; i < lenB; ++i) { if(mp[(int)B[i]] == -1) { mp[(int)B[i]] = m++; vs.push_back((int)B[i]); } } sort(vs.begin(), vs.end()); m = 0; for(int i = 0; i < (int)vs.size(); ++i) { int ch = vs[i]; mp[ch] = m++; } SA(); } int main(int argc, char const *argv[]) { int T; scanf("%d", &T); getchar(); while(T--){ gets(B); gets(A); lenB = strlen(B), lenA = strlen(A); init(); solve(); } return 0; }