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|∗NumberoftimesSoccuringinT

Jane 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|≤ 105

Sample Input #00
aaaaaa
Sample Output #00
12
Explanation #00
f('a') = 6

f('aa') = 10

f('aaa') = 12

f('aaaa') = 12

f('aaaaa') = 10

f('aaaaaa') = 6
Sample Input #01
abcabcddd
Sample Output #01
9
Explanation #01
f("a") = 2

f("b") = 2

f("c") = 2

f("ab") = 4

f("bc") = 4

f("ddd") = 3

f("abc") = 6

f("abcabcddd") = 9
Among the function values 9 is the maximum one.

题意：求字符串所有子串中，f(s)的最大值。这里ｓ是某个子串，f(s)　＝　ｓ的长度与ｓ在原字符串中出现次数的乘积。

求得lcp, 转化为求以lcp为高的最大子矩形。

Accepted Code:

 #include <string>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int MAX_N = ;

 int sa[MAX_N], rk[MAX_N], lcp[MAX_N], tmp[MAX_N], n, k;

 bool compare_sa(int i, int j) {

     if (rk[i] != rk[j]) return rk[i] < rk[j];

     int ri = i + k <= n ? rk[i + k] : -;

     int rj = j + k <= n ? rk[j + k] : -;

     return ri < rj;

 }

 void construct_sa(const string &S, int *sa) {

     n = S.length();

     for (int i = ; i <= n; i++) {

         sa[i] = i;

         rk[i] = i < n ? S[i] : -;

     }

     for (k = ; k <= n; k *= ) {

         sort(sa, sa + n + , compare_sa);

         tmp[sa[]] = ;

         for (int i = ; i <= n; i++) {

             tmp[sa[i]] = tmp[sa[i - ]] + (compare_sa(sa[i - ], sa[i]) ?  : );

         }

         for (int i = ; i <= n; i++) rk[i] = tmp[i];

     }

 }

 void construct_lcp(const string &S, int *sa, int *lcp) {

     n = S.length();

     for (int i = ; i <= n; i++) rk[sa[i]] = i;

     int h = ;

     lcp[] = ;

     for (int i = ; i < n; i++) {

         int j = sa[rk[i] - ];

         if (h > ) h--;

         for (; i + h < n && j + h < n; h++) if (S[i + h] != S[j + h]) break;

         lcp[rk[i] - ] = h;

     }

 }

 string S;

 int lft[MAX_N], rgt[MAX_N], st[MAX_N], top;

 void solve() {

     construct_sa(S, sa);

     construct_lcp(S, sa, lcp);

     lcp[n] = n - sa[n];

    // for (int i = 1; i <= n; i++) cerr << lcp[i] << ' ';

    // cerr << endl;

     top = ;

     for (int i = ; i <= n; i++) {

         while (top && lcp[st[top-]] >= lcp[i]) top--;

         if (top) lft[i] = st[top - ] + ;

         else lft[i] = ;

         st[top++] = i;

     }

     top = ;

     for (int i = n; i > ; i--) {

         while (top && lcp[st[top-]] >= lcp[i]) top--;

         // attention: rgt[i] should be asigned to st[top - 1]

         // rather than st[top - 1] - 1 because lcp[i] is the

         // length of the longest common prefix of sa[i] and sa[i + 1].

         if (top) rgt[i] = st[top - ];

         else rgt[i] = n;

         st[top++] = i;

     }

     long long ans = n;

     for (int i = ; i <= n; i++) ans = max(ans, (long long)lcp[i] * (rgt[i] - lft[i] + ));

     cout << ans << endl;

 }

 int main(void) {

     //ios::sync_with_std(false);

     while (cin >> S) solve();

     return ;

 }

巴特西

Hackerrank--String Function Calculation(后缀数组）

最新文章

热门文章