haskell - Hackerrank 字符串函数计算

Question

我正在尝试解决Hackerrank 的字符串函数计算问题。在这个问题中，我们给定一个字符串作为输入，并要求在输入字符串的所有子字符串中打印一个表示以下函数最大值的数字：

f(s, t) = 子字符串 's' 在字符串 't' 中出现的次数 * 子字符串 's' 的长度

我提交了以下内容作为答案：

import Data.List

main :: IO()
main = do
    stringInput <- getLine
    print $ solution stringInput

solution :: String -> Int
solution input = maximum $ map sum $ map (map length) $ group $ sort $ substrings input

substrings :: String -> [String]
substrings s = tail . inits =<< tails s

这个想法是：

1. 获取s.let s = "aaaaaa"; substrings s = ["a","aa","aaa","aaaa","aaaaa","aaaaaa","a","aa","aaa","aaaa","aaaaa","a","aa","aaa","aaaa","a","aa","aaa","a","aa","a"]

2. 解决。["a","a","a","a","a","a","aa","aa","aa","aa","aa","aaa","aaa","aaa","aaa","aaaa" ,"aaaa","aaaa","aaaaa","aaaaa","aaaaaa"]

3. 将其分组。[["a","a","a","a","a","a"],["aa","aa","aa","aa","aa"],["aaa","aaa","aaa","aaa"],["aaaa","aaaa","aaaa"],["aaaaa","aaaaa"],["aaaaaa"]]

4. 获取每个子字符串的单独长度。[[1,1,1,1,1,1],[2,2,2,2,2],[3,3,3,3],[4,4,4],[5,5],[6]]

5. 对结果列表求和。[6,10,12,12,10,6].

6. 获得最大值。12.

这通过了初步测试。但是，当我提交它时，它会因“运行时错误”而失败所有其他测试。

测试用例编号 2、第一个失败，运行1.47秒，输入如下：

"aacbbabbabbbbbaaaaaaabbbbcacacbcabaccaabbbcaaabbccccbbbcbccccbbcaabaaabcbaacbcbaccaaaccbccbcaacbaccbaacbbabbabbbbbaaaaaaabbbbcacacbcabaccaabbbcaaabbccccbbbcbccccbbcaabaaabcbaacbcbaccaaaccbccbcaacbaccbaacbbabbabbbbbaaaaaaabbbbcacacbcabaccaabbbcaaabbccccbbbcbccccbbcaabaaabcbaacbcbaccaaaccbccbcaacbaccbaacbbabbabbbbbaaaaaaabbbbcacacbcabaccaabbbcaaabbccccbbbcbccccbbcaabaaabcbaacbcbaccaaaccbccbcaacbaccbaacbbabbabbbbbaaaaaaabbbbcacacbcabaccaabbbcaaabbccccbbbcbccccbbcaabaaabcbaacbcbaccaaaccbccbcaacbaccb"

你能帮我弄清楚我做错了什么，或者发生了什么吗？

Answer 1

这行不通。排序变得非常昂贵（内存方面），因为此列表中的中间
产品保留在内存中并且这些产品很大。这是内存
错误

更好的方法是使用后缀数组 ，然后使用创建 最长前缀数组 (LCP) ，然后将 LCP 数组用于 问题的其余部分。 O(n log2n)
Kasai's Algorithm in O(n)

计算LCP[i] and LCP[i+1] 如果它们相等，则表示有两个相等的子字符串，这样继续。

Answer 2

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

#define nb nexta
#define head height
#define rank b

const int maxn = 100010;
char s[maxn];
int n, id[maxn], height[maxn], b[maxn], nexta[maxn];

bool cmp(const int& i, const int& j)
{
    return s[i] < s[j];
}

void SuffixSort()
{
    int i, j, k, h;
    for (i = 0; i < n; i++) id[i] = i;
    sort(id, id + n, cmp);
    for (i = 0; i < n; i++)
    {
        if (i == 0 || s[id[i]] != s[id[i - 1]])
            b[id[i]] = i;
        else b[id[i]] = b[id[i - 1]];
    }
    for (h = 1; h < n; h <<= 1)
    {
        for (i = 0; i < n; i++)
            head[i] = nexta[i] = -1;
        for (i = n - 1; i >= 0; i--)
        {
            if (id[i])
            {
                j = id[i] - h;
                if (j < 0) j += n;
                nexta[j] = head[b[j]];
                head[b[j]] = j;
            }
        }
        j = n - h;
        nexta[j] = head[b[j]];
        head[b[j]] = j;
        for (i = k = 0; i < n; i++)
            if (head[i] >= 0)
                for (j = head[i]; j >= 0; j = nexta[j])
                    id[k++] = j;
        for (i = 0; i < n; i++)
            if (i>0 && id[i] + h < n&&id[i - 1] + h < n&&b[id[i]] == b[id[i - 1]] && b[id[i] + h] == b[id[i - 1] + h])
                nb[id[i]] = nb[id[i - 1]];
            else
                nb[id[i]] = i;
        for (i = 0; i < n; i++)
            b[i] = nb[i];
    }
}

void GetHeight()
{
    int i, j, h; height[0] = 0;
    for (i = 0; i < n; i++)
        rank[id[i]] = i;
    for (h = 0, i = 0; i < n; i++)
    {
        if (rank[i] > 0)
        {
            j = id[rank[i] - 1];
            while (s[i + h] == s[j + h])++h;
            height[rank[i]] = h;
            if (h>0) --h;
        }
    }
}

int st[maxn], top;

int main()
{
    cin >> s;
    n = strlen(s);
    top = 0;
    SuffixSort();
    GetHeight();
    height[n] = 0;
    int best = n;
    st[top++] = 0;
    for (int i = 1; i < n + 1; i++)
    {
        //cout << height[i] << " ";
        while (top != 0 && height[i] < height[st[top - 1]])
        {
            int val = height[st[top - 1]];
            top--;
            best = max(best, val * (top == 0 ? i : i - st[top - 1]));
        }

        if (top == 0 || height[i] >= height[st[top - 1]])
            st[top++] = i;
    }
    cout << best << endl;
    return 0;
}