Самая длинная подпоследовательность со всеми вхождениями персонажа в 1 месте

Question

В последовательности S из n символов; каждый символ может встречаться много раз в последовательности. Вы хотите найти самую длинную подпоследовательность S, где все вхождения одного и того же символа находятся вместе в одном месте;

Например если S = ​​aaaccaaaccbccbbbab, то самая длинная такая подпоследовательность (ответ) - это aaaaaaccccbbbb, т.е. = aaa__aaacc_ccbbb_b.

Другими словами, любой символ алфавита, который появляется в S, может появляться только в одном непрерывном блоке в подпоследовательности. Если возможно, приведите алгоритм полиномиального времени для определения решения.

Answer 1

дизайн

Ниже я приведу реализацию алгоритма динамического программирования на C++, которая решает эту проблему. Верхняя граница времени выполнения (которая, вероятно, не жесткая) задается как O(g*(n^2 + log(g))), где n - длина строки, а g - количество различных подпоследовательностей в вход. Я не знаю хорошего способа охарактеризовать это число, но оно может быть таким же плохим, как O(2^n) для строки, состоящей из n различных символов, что делает этот алгоритм экспоненциально-временным в худшем случае. Он также использует пространство O(ng) для хранения таблицы воспоминаний DP. (Подпоследовательность, в отличие от подстроки, может состоять из несмежного символа из исходной строки.) На практике алгоритм будет быстрым всякий раз, когда количество различных символов мало.

Две ключевые идеи, использованные при разработке этого алгоритма:

• Каждая подпоследовательность строки длины n является либо (а) пустой строкой, либо (б) подпоследовательностью, первый элемент которой находится в некоторой позиции 1 <= i <= n и за которой следует другая подпоследовательность суффикса, начинающаяся в позиции i+1.
• Если мы добавляем символы (или, более конкретно, позиции символов) по одному к подпоследовательности, то для построения всех и только подпоследовательностей, которые удовлетворяют критериям достоверности, всякий раз, когда мы добавляем символ c, если добавлен предыдущий символ, p, отличался от c, то больше нельзя было добавить какие-либо символы p позже.

Есть как минимум 2 способа справиться со вторым пунктом выше. Один из способов - сохранить набор запрещенных символов (например, используя 256-битный массив), который мы добавляем по мере добавления символов в текущую подпоследовательность. Каждый раз, когда мы хотим добавить символ в текущую подпоследовательность, мы сначала проверяем, разрешено ли это.

Другой способ - понять, что всякий раз, когда нам нужно запретить символу появляться позже в подпоследовательности, мы можем добиться этого, просто удалив все копии символа из оставшегося суффикса и используя эту (возможно, более короткую) строку в качестве подзадачи для решения рекурсивно. Преимущество этой стратегии состоит в том, что она повышает вероятность того, что решающая функция будет вызываться несколько раз с одним и тем же строковым аргументом, что означает, что можно избежать дополнительных вычислений при преобразовании рекурсии в DP. Вот как работает код ниже.

Рекурсивная функция должна принимать 2 параметра: строку для работы и последний символ, добавленный к подпоследовательности, к которой будет добавлен вывод функции. Второй параметр должен иметь специальное значение, указывающее, что еще не добавлено ни одного символа (что происходит в рекурсивном случае верхнего уровня). Один из способов сделать это - выбрать символ, который не отображается во входной строке, но это вводит требование не использовать этот символ. Очевидный обходной путь - передать третий параметр, логическое значение, указывающее, были ли уже добавлены какие-либо символы. Но немного удобнее использовать только 2 параметра: логическое значение, указывающее, были ли еще добавлены какие-либо символы, и строка. Если логическое значение false, то строка - это просто строка, с которой нужно работать. Если это правда, то первый символ строки считается последним добавленным символом, а остальная часть является строкой, над которой нужно работать. Принятие этого подхода означает, что функция принимает только 2 параметра, что упрощает запоминание.

Как я уже говорил вверху, в худшем случае этот алгоритм имеет экспоненциальное время. Я не могу придумать, как полностью этого избежать, но некоторые оптимизации могут помочь в определенных случаях. Я реализовал один способ - всегда добавлять максимально непрерывные блоки одного и того же символа за один шаг, поскольку, если вы добавите хотя бы один символ из такого блока, никогда не будет оптимальным добавлять меньше, чем весь блок. Возможны другие оптимизации стиля ветвления и границ, такие как отслеживание пока что лучшей в мире строки и сокращение рекурсии всякий раз, когда мы можем быть уверены, что текущая подзадача не может создать более длинную, например, когда число символов добавленный к подпоследовательности, плюс общее количество оставшихся символов меньше, чем длина лучшей подпоследовательности до сих пор.

Код

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <map>

using namespace std;

class RunFinder {
    string s;
    map<string, string> memo[2];    // DP matrix

    // If skip == false, compute the longest valid subsequence of t.
    // Otherwise, compute the longest valid subsequence of the string
    // consisting of t without its first character, taking that first character
    // to be the last character of a preceding subsequence that we will be
    // adding to.
    string calc(string const& t, bool skip) {
        map<string, string>::iterator m(memo[skip].find(t));

        // Only calculate if we haven't already solved this case.
        if (m == memo[skip].end()) {
            // Try the empty subsequence.  This is always valid.
            string best;

            // Try starting a subsequence whose leftmost position is one of
            // the remaining characters.  Instead of trying each character
            // position separately, consider only contiguous blocks of identical
            // characters, since if we choose one character from this block there
            // is never any harm in choosing all of them.
            for (string::const_iterator i = t.begin() + skip; i != t.end();) {
            if (t.end() - i < best.size()) {
                // We can't possibly find a longer string now.
                break;
            }

                string::const_iterator next = find_if(i + 1, t.end(), bind1st(not_equal_to<char>(), *i));
                // Just use next - 1 to cheaply give us an extra char at the start; this is safe
                string u(next - 1, t.end());
                u[0] = *i;      // Record the previous char for the recursive call
                if (skip && *i != t[0]) {
                    // We have added a new segment that is different from the
                    // previous segment.  This means we can no longer use the
                    // character from the previous segment.
                    u.erase(remove(u.begin() + 1, u.end(), t[0]), u.end());
                }
                string v(i, next);
                v += calc(u, true);

                if (v.size() > best.size()) {
                    best = v;
                }

                i = next;
            }

            m = memo[skip].insert(make_pair(t, best)).first;
        }

        return (*m).second;
    }

public:
    RunFinder(string s) : s(s) {}

    string calc() {
        return calc(s, false);
    }
};

int main(int argc, char **argv) {
    RunFinder rf(argv[1]);
    cout << rf.calc() << '\n';
    return 0;
}

Пример результатов

C:\runfinder>stopwatch runfinder aaaccaaaccbccbbbab
aaaaaaccccbbbb
stopwatch: Terminated. Elapsed time: 0ms
stopwatch: Process completed with exit code 0.

C:\runfinder>stopwatch runfinder abbaaasdbasdnfa,mnbmansdbfsbdnamsdnbfabbaaasdbasdnfa,mnbmansdbfsbdnamsdnbfabbaaasdbasdnfa,mnbmansdbfsbdnamsdnbfabbaaasdbasdnfa,mnbmansdbfsbdnamsdnbf
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa,mnnsdbbbf
stopwatch: Terminated. Elapsed time: 609ms
stopwatch: Process completed with exit code 0.

C:\runfinder>stopwatch -v runfinder abcdefghijklmnopqrstuvwxyz123456abcdefghijklmnop
stopwatch: Command to be run: <runfinder abcdefghijklmnopqrstuvwxyz123456abcdefghijklmnop>.
stopwatch: Global memory situation before commencing: Used 2055507968 (49%) of 4128813056 virtual bytes, 1722564608 (80%) of 2145353728 physical bytes.
stopwatch: Process start time: 21/11/2012 02:53:14
abcdefghijklmnopqrstuvwxyz123456
stopwatch: Terminated. Elapsed time: 8062ms, CPU time: 7437ms, User time: 7328ms, Kernel time: 109ms, CPU usage: 92.25%, Page faults: 35473 (+35473), Peak working set size: 145440768, Peak VM usage: 145010688, Quota peak paged pool usage: 11596, Quota peak non paged pool usage: 1256
stopwatch: Process completed with exit code 0.
stopwatch: Process completion time: 21/11/2012 02:53:22

Последний запуск, который занял 8 секунд и использовал 145 МБ, показывает, как могут возникнуть проблемы со строками, содержащими много разных символов.

РЕДАКТИРОВАТЬ: Добавлено в другой оптимизации: теперь мы выходим из цикла, который ищет место для запуска подпоследовательности, если мы можем доказать, что она не может быть лучше, чем лучший из обнаруженных до сих пор. Это уменьшает время, необходимое для последнего примера, с 32 до 8 секунд!

Answer 2

РЕДАКТИРОВАТЬ: Это решение не подходит для проблемы ОП. Я не удаляю это, потому что это могло бы быть правильным для кого-то еще.:)

Рассмотрим связанную проблему: найдите самую длинную подпоследовательность S последовательных вхождений данного символа. Это можно решить за линейное время:

char c = . . .; // the given character
int start = -1;
int bestStart = -1;
int bestLength = 0;
int currentLength = 0;
for (int i = 0; i < S.length; ++i) {
    if (S.charAt(i) == c) {
        if (start == -1) {
            start = i;
        }
        ++currentLength;
    } else {
        if (currentLength > bestLength) {
            bestStart = start;
            bestLength = currentLength;
        }
        start = -1;
        currentLength = 0;
    }
}
if (bestStart >= 0) {
    // longest sequence of c starts at bestStart
} else {
    // character c does not occur in S
}

Если количество отдельных символов (назовите его m) достаточно маленький, просто примените этот алгоритм параллельно к каждому символу. Это может быть легко сделано путем преобразования start, bestStart, currentLength, bestLength к массивам m долго. В конце отсканируйте bestLength массив для индекса наибольшей записи и использовать соответствующую запись в bestStart массив как ваш ответ. Общая сложность O(mn).

Answer 3

import java.util.*;

public class LongestSubsequence {

    /**
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String str = sc.next();

        execute(str);

    }


    static void execute(String str) {

        int[] hash = new int[256];
        String ans = "";

        for (int i = 0; i < str.length(); i++) {

            char temp = str.charAt(i);

            hash[temp]++;
        }

        for (int i = 0; i < hash.length; i++) {
            if (hash[i] != 0) {
                for (int j = 0; j < hash[i]; j++)
                    ans += (char) i;
            }
        }

        System.out.println(ans);
    }
}

Пробел: 256 -> O(256), я не знаю, если это правильно сказать так..., потому что O (256) Я думаю, что O(1) Время: O(n)