Наибольшая длина строки префикса для всех суффиксов

Question

Найти длину самой длинной строки префикса для всех суффиксов строки.

Например, суффиксами строки ababaa являются ababaa, babaa, abaa, baa, aa и a. Сходство каждой из этих строк со строкой «ababaa» составляет 6,0,3,0,1,1 соответственно. Таким образом, ответ 6 + 0 + 3 + 0 + 1 + 1 = 11.

Я написал следующий код

#include <iostream>
#include <string.h>

#include <stdio.h>
#include <time.h>

int main ( int argc, char **argv) {
    size_t T;
    std::cin >> T;
    char input[100000];
    for ( register size_t i = 0; i < T; ++i) {
        std::cin >> input;

        double t = clock();

        size_t len    = strlen(input);
        char *left    = input;
        char *right   = input + len - 1;
        long long sol = 0;
        int end_count = 1;
        while ( left < right ) {
            if ( *right != '\0') {
                if ( *left++ == *right++ ) {
                    sol++;
                    continue;
                }
            }
            end_count++;
            left = input; // reset the left pointer
            right = input + len - end_count; // set right to one left.
        }
        std::cout << sol + len << std::endl;
        printf("time= %.3fs\n", (clock() - t) / (double)(CLOCKS_PER_SEC));
    }
}

Работает нормально, но для строки длиной 100000, имеющей тот же символ, т. Е. aaaaaaaaaa.......a, требуется много времени, как я могу оптимизировать эту еще одну.

Answer 1

Вы можете использовать суффиксный массив: http://en.wikipedia.org/wiki/Suffix_array

Answer 2

Используйте алгоритм Z для вычисления длины всех подстрок, который также префиксов в O(n), а затем сканирует результирующий массив и суммирует его значения.

Answer 3

Допустим, ваш ababaa является паттерном P. Я думаю, что вы могли бы использовать следующий алгоритм:

1. Создать суффикс автоматов для всех возможных суффиксов P.
2. Пройдите по автоматам, используя P в качестве входных данных, подсчитайте количество пройденных ребер. Для каждого принимающего состояния автоматов добавьте текущее число ребер к общей сумме. Пройдите до автомата, пока не достигнете конца ввода или не останется больше ребер для прохождения.
3. Итоговая сумма - результат.

Answer 4

Вот реализация Java:

        // sprefix
        String s = "abababa";
        Vector<Integer>[] v = new Vector[s.length()];
        int sPrefix = s.length();
        v[0] = new Vector<Integer>();
        v[0].add(new Integer(0));
        for(int j = 1; j < s.length(); j++)
        {
            v[j] = new Vector<Integer>();
            v[j].add(new Integer(0));
            for(int k = 0; k < v[j - 1].size(); k++)
                if(s.charAt(j) == s.charAt(v[j - 1].get(k)))
                {
                    v[j].add(v[j - 1].get(k) + 1);
                    v[j - 1].set(k, 0);
                }
        }

        for(int j = 0; j < v.length; j++)
            for(int k = 0; k < v[j].size(); k++)
                sPrefix += v[j].get(k);

        System.out.println("Result = " + sPrefix);

Answer 5

Я не уверен, что Trie дает вам прирост производительности ... но я бы наверняка подумал об этом.

Другая идея, которая у меня была, - попытаться сжать вашу строку.Я не задумывался об этом, просто сумасшедшая идея ...

если у вас есть такая строка: ababaa сжать ее, может быть, до: abab2a.Затем вы должны придумать технику, в которой вы можете использовать свой алгоритм с этими строками.Преимущество состоит в том, что вы можете эффективно сравнить длинные строки 100000a друг с другом.Или, что более важно: вы можете очень быстро рассчитать свою сумму.

Но опять же, я не продумал это, может быть, это очень плохая идея;)

Answer 6

Из того, что я вижу, вы используете простой массив для оценки суффикса, и, хотя он может оказаться эффективным для некоторого набора данных, в некоторых случаях он будет неэффективным, например, тот, который вы упомянули.

Вам необходимо реализовать Дерево префиксов или Trie , подобное Структуре данных.Код для них не прост, поэтому, если вы не знакомы с ними, я бы посоветовал вам немного прочитать о них.