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

Ответ 1

Дизайн

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

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

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

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

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

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

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

код

#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 Мб, показывает, как он может иметь проблемы со строками, содержащими много разных символов.

EDIT:Добавлена ​​еще одна оптимизация: теперь мы выходим из цикла, который ищет место для начала подпоследовательности, если мы сможем доказать, что он не может быть лучше, чем тот, который был обнаружен до сих пор. Это уменьшает время, необходимое для последнего примера с 32 до 8 с!

Ответ 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 long. В конце сканируйте массив bestLength для индекса наибольшей записи и используйте соответствующую запись в массиве bestStart в качестве своего ответа. Общая сложность O (mn).

Ответ 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)