Longest Common Substring
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4077 Accepted Submission(s): 1544Problem DescriptionGiven two strings, you have to tell the length of the Longest Common Substring of them.
For example:
str1 = banana
str2 = cianaic
So the Longest Common Substring is "ana", and the length is 3.
InputThe input contains several test cases. Each test case contains two strings, each string will have at most 100000 characters. All the characters are in lower-case.
Process to the end of file.
OutputFor each test case, you have to tell the length of the Longest Common Substring of them.
Sample Inputbanana cianaic
Sample Output3
1 /*************************************************************************
2 > File Name: 1403.cpp
3 > Author: Stomach_ache
4 > Mail: sudaweitong@gmail.com
5 > Created Time: 2014年08月22日 星期五 09时00分05秒
6 > Propose: sa + lcp
7 ************************************************************************/
8
9 #include <cmath>
10 #include <string>
11 #include <cstdio>
12 #include <fstream>
13 #include <cstring>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 /*Let‘s fight!!!*/
18
19 const int MAX_N = 100005 << 1;
20 int n, k;
21 int sa[MAX_N], lcp[MAX_N], rank[MAX_N], tmp[MAX_N];
22
23 bool compare_sa(int i, int j) {
24 if (rank[i] != rank[j]) return rank[i] < rank[j];
25 else {
26 int ri = i + k <= n ? rank[i + k] : -1;
27 int rj = j + k <= n ? rank[j + k] : -1;
28 return ri < rj;
29 }
30 }
31
32 void construct_sa(const string &S, int *sa) {
33 n = S.length();
34
35 for (int i = 0; i <= n; i++) {
36 sa[i] = i;
37 rank[i] = i < n ? S[i] : -1;
38 }
39
40 for (k = 1; k <= n; k *= 2) {
41 sort(sa, sa + n + 1, compare_sa);
42
43 tmp[sa[0]] = 0;
44 for (int i = 1; i <= n; i++) {
45 tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
46 }
47 for (int i = 0; i <= n; i++) rank[i] = tmp[i];
48 }
49 }
50
51 void construct_lcp(const string &S, int *sa, int *lcp) {
52 int n = S.length();
53 for (int i = 0; i <= n; i++) rank[sa[i]] = i;
54
55 int h = 0;
56 lcp[0] = 0;
57 for (int i = 0; i < n; i++) {
58 int j = sa[rank[i] - 1];
59
60 if (h > 0) h--;
61 for (; j + h < n && i + h < n; h++) if (S[i + h] != S[j + h]) break;
62
63 lcp[rank[i] - 1] = h;
64 }
65 }
66
67 string S, T;
68
69 void solve() {
70 int len1 = S.length();
71 S = S + ‘$‘ + T;
72
73 construct_sa(S, sa);
74 construct_lcp(S, sa, lcp);
75
76 int ans = 0;
77 for (unsigned i = 0; i < S.length(); i++) {
78 if ((sa[i] < len1) != (sa[i + 1] < len1))
79 ans = max(ans, lcp[i]);
80 }
81 cout << ans << endl;
82 }
83
84 int main(void) {
85 ios::sync_with_stdio(false);
86 while (cin >> S >> T) {
87 solve();
88 }
89 return 0;
90 }
原文：http://www.cnblogs.com/Stomach-ache/p/3928852.html