Самая длинная подпоследовательность со всеми вхождениями символа на 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 параметра, что упрощает запоминание.

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

Код

#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 с!

EDIT: это решение неверно для проблемы OP. Я не удаляю это, потому что это может быть правильным для кого-то еще. :)

Рассмотрим родственную задачу: найти самую длинную подпоследовательность 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).

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)