首页 > 代码库 > Hackerrank--String Function Calculation(后缀数组）
Hackerrank--String Function Calculation(后缀数组）
题目链接
Jane loves string more than anything. She made a function related to the string some days ago and forgot about it. She is now confused about calculating the value of this function. She has a string T with her, and value of string S over function f can be calculated as given below:
f(S)=|S|∗NumberoftimesSoccuringinTJane wants to know the maximum value of f(S) among all the substrings (S) of string T. Can you help her?
Input Format
A single line containing string T in small letter(‘a‘ - ‘z‘).Output Format
An integer containing the value of output.Constraints
1 ≤|T|≤ 105Sample Input #00
aaaaaaSample Output #00
12Explanation #00
f(‘a‘) = 6f(‘aa‘) = 10f(‘aaa‘) = 12f(‘aaaa‘) = 12f(‘aaaaa‘) = 10f(‘aaaaaa‘) = 6Sample Input #01
abcabcdddSample Output #01
9Explanation #01
f("a") = 2f("b") = 2f("c") = 2f("ab") = 4f("bc") = 4f("ddd") = 3f("abc") = 6f("abcabcddd") = 9Among the function values 9 is the maximum one.
题意：求字符串所有子串中，f(s)的最大值。这里ｓ是某个子串，f(s) ＝ ｓ的长度与ｓ在原字符串中出现次数的乘积。
求得lcp, 转化为求以lcp为高的最大子矩形。
Accepted Code:
1 #include <string> 2 #include <iostream> 3 #include <algorithm> 4 using namespace std; 5 6 const int MAX_N = 100002; 7 int sa[MAX_N], rk[MAX_N], lcp[MAX_N], tmp[MAX_N], n, k; 8 9 bool compare_sa(int i, int j) {10 if (rk[i] != rk[j]) return rk[i] < rk[j];11 int ri = i + k <= n ? rk[i + k] : -1;12 int rj = j + k <= n ? rk[j + k] : -1;13 return ri < rj;14 }15 16 void construct_sa(const string &S, int *sa) {17 n = S.length();18 for (int i = 0; i <= n; i++) {19 sa[i] = i;20 rk[i] = i < n ? S[i] : -1;21 }22 23 for (k = 1; k <= n; k *= 2) {24 sort(sa, sa + n + 1, compare_sa);25 26 tmp[sa[0]] = 0;27 for (int i = 1; i <= n; i++) {28 tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);29 }30 for (int i = 0; i <= n; i++) rk[i] = tmp[i];31 }32 }33 34 void construct_lcp(const string &S, int *sa, int *lcp) {35 n = S.length();36 for (int i = 0; i <= n; i++) rk[sa[i]] = i;37 38 int h = 0;39 lcp[0] = 0;40 for (int i = 0; i < n; i++) {41 int j = sa[rk[i] - 1];42 43 if (h > 0) h--;44 for (; i + h < n && j + h < n; h++) if (S[i + h] != S[j + h]) break;45 46 lcp[rk[i] - 1] = h;47 }48 }49 50 string S;51 int lft[MAX_N], rgt[MAX_N], st[MAX_N], top;52 void solve() {53 construct_sa(S, sa);54 construct_lcp(S, sa, lcp);55 56 lcp[n] = n - sa[n];57 // for (int i = 1; i <= n; i++) cerr << lcp[i] << ‘ ‘;58 // cerr << endl;59 top = 0;60 for (int i = 1; i <= n; i++) {61 while (top && lcp[st[top-1]] >= lcp[i]) top--;62 if (top) lft[i] = st[top - 1] + 1;63 else lft[i] = 1;64 st[top++] = i;65 }66 top = 0;67 for (int i = n; i > 0; i--) {68 while (top && lcp[st[top-1]] >= lcp[i]) top--;69 // attention: rgt[i] should be asigned to st[top - 1]70 // rather than st[top - 1] - 1 because lcp[i] is the71 // length of the longest common prefix of sa[i] and sa[i + 1]. 72 if (top) rgt[i] = st[top - 1];73 else rgt[i] = n;74 st[top++] = i;75 }76 long long ans = n;77 for (int i = 1; i <= n; i++) ans = max(ans, (long long)lcp[i] * (rgt[i] - lft[i] + 1));78 cout << ans << endl;79 }80 81 int main(void) {82 //ios::sync_with_std(false);83 while (cin >> S) solve();84 return 0;85 }
Hackerrank--String Function Calculation(后缀数组）