Найти дублированный контент в строке?

Question

Как бы вы решили следующую проблему:

У меня есть небольшой файл с текстом (около 10 страниц), и я хочу найти дублированный контент в этом тексте.Чтобы быть более точным, учитывая строку, найдите две самые длинные строки, которые идентичны.

Я искал самую длинную общую подпоследовательность:

http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Longest_common_subsequence

Но эти реализации принимают в качестве входных данных две строки.

Может быть, служба уже делает это?

Answer 1

Вот простой (но неэффективный) алгоритм: зациклите все возможные длины подстрок от максимальной до 1. Для каждой длины поместите все подстроки этой длины в словарь. Если вы найдете дубликат, остановитесь. Это должен быть самый большой. Вот соответствующий код C #:

    public static string FindDuplicateSubstring(string s)
    {
        for (int len = s.Length-1; len > 0; len--) {
            var dict = new Dictionary<string, int>();
            for (int i = 0; i <= s.Length - len; i++) {
                string sub = s.Substring(i, len);
                if (dict.ContainsKey(sub)) return sub;
                else dict[sub] = i;
            }
        }
        return null;
    }

Например, применительно к тексту вашего вопроса самая длинная повторяющаяся подстрока - это "реализация". Обратите внимание, что допускаются перекрывающиеся подстроки, т. Е. Вход «bbbb» возвращает «bbb». Из твоего вопроса не было ясно, хочешь ли ты исключить перекрывающийся случай. Для более быстрого подхода см. Мой другой ответ.

Answer 2

Алгоритм «Самая длинная общая подпоследовательность» не требует, чтобы совпадения были смежными подстроками. Например, для строк «компьютер» и «плавучий дом» подпоследовательность «вне». Это то, что вы хотите?

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

Если вы хотите что-то короткое и простое, вот подход, основанный на алгоритме LCS, но без таблицы. Идея состоит в том, чтобы зациклить все возможные целочисленные сдвиги между желаемой подстрокой и ее дубликатом. Для каждой смены найдите наибольшее непрерывное совпадение, отсканировав строку один раз. Если входная строка имеет длину n, существует O (n) возможных сдвигов, и проверка каждого сдвига занимает O (n) времени, поэтому общая стоимость составляет O (n ^ 2) с постоянным количеством места. (Сравните с моим простым словарным ответом, который занимает O (n ^ 3) времени и O (n ^ 2) пробела.) Если вы не хотите, чтобы совпадающие совпадения (т.е. вы хотите, чтобы «bbbb» возвращал «bb», а не «bbb») ), то при проверке каждой смены вы останавливаетесь, если наибольшее совпадение превышает смену. Вот код C #:

    public static string FindDuplicateSubstring(string s, 
                                                bool allowOverlap = false)
    {
        int matchPos = 0, maxLength = 0;
        for (int shift = 1; shift < s.Length; shift++) {
            int matchCount = 0;
            for (int i = 0; i < s.Length - shift; i++) {
                if (s[i] == s[i+shift]) {
                    matchCount++;
                    if (matchCount > maxLength) {
                        maxLength = matchCount;
                        matchPos = i-matchCount+1;
                    }
                    if (!allowOverlap && (matchCount == shift)) {
                        // we have found the largest allowable match 
                        // for this shift.
                        break;
                    }
                } else matchCount = 0;
            }
        }
        if (maxLength > 0) return s.Substring(matchPos, maxLength);
        else return null;
    }

Я проверил это по своему словарному ответу, и он дает те же результаты. Но для случайной строки длиной 3000 словарю требуется 15 секунд, в то время как описанный выше метод занимает 60 мс (и намного меньше памяти).

Answer 3

Вы можете сделать что-то подобное

Answer 4

попробуйте

public static string FindLargestDuplicateString(
        string text)
    {
        var largest = string.Empty;
        for (var i = '!'; i <= '}'; i++)
        {
            var l = FindLargestDuplicateStringImpl(
                text, i.ToString());
            if (l.Length > largest.Length)
                largest = l;
        }
        return largest;
    }

    private static string FindLargestDuplicateStringImpl(
        string text, string currentLargest)
    {
        bool found = false;
        for (var i = '!'; i <= '}'; i++)
        {
            var comp = currentLargest + i;
            var last = text.LastIndexOf(comp);
            var first = text.IndexOf(comp, 0);
            if (first == -1 || last == -1 || first == last) 
                continue;
            currentLargest = comp;
            found = true;
        }
        return !found ? currentLargest : 
            FindLargestDuplicateStringImpl(text, currentLargest);
    }