Расчет функции Hackerrank String

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,

Это проходит предварительные испытания. Тем не менее, когда я отправляю его, он не проходит все остальные тесты по "Runtime Error".

Контрольный пример № 2, первый отказавший, занимает 1,47 секунды и имеет следующий вход:

"aacbbabbabbbbbaaaaaaabbbbcacacbcabaccaabbbcaaabbccccbbbcbccccbbcaabaaabcbaacbcbaccaaaccbccbcaacbaccbaacbbabbabbbbbaaaaaaabbbbcacacbcabaccaabbbcaaabbccccbbbcbccccbbcaabaaabcbaacbcbaccaaaccbccbcaacbaccbaacbbabbabbbbbaaaaaaabbbbcacacbcabaccaabbbcaaabbccccbbbcbccccbbcaabaaabcbaacbcbaccaaaccbccbcaacbaccbaacbbabbabbbbbaaaaaaabbbbcacacbcabaccaabbbcaaabbccccbbbcbccccbbcaabaaabcbaacbcbaccaaaccbccbcaacbaccbaacbbabbabbbbbaaaaaaabbbbcacacbcabaccaabbbcaaabbccccbbbcbccccbbcaabaaabcbaacbcbaccaaaccbccbcaacbaccb"

Не могли бы вы помочь мне выяснить, что я делаю неправильно или что происходит?

Answer 1

Это не сработает. Сортировка становится очень дорогой (с точки зрения памяти) в качестве промежуточного
Продукты в этом списке остаются в памяти, и эти продукты являются большими. Это память
ошибка

Лучше было бы использовать суффиксные массивы O(n log2n) а затем создать
самый длинный префиксный массив (LCP) с использованием Kasai's Algorithm in O(n) а затем использовать массив LCP для
Остальная часть проблемы.

подсчитывать 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;
}