Алгоритм, если есть строка, включающая подпоследовательности A и B, но не F

Question

Я ищу эффективный алогрит для следующей задачи:

Нам даны в качестве входных данных три строки A, B и F, и нам нужно сказать, есть ли строка X такая, что A и Bявляются подпоследовательностями X, а F нет.Вывод алгоритма должен быть «Да» или «Нет».

Подпоследовательность строки - это любая строка, которая может быть создана путем удаления некоторых букв из исходной строки без изменения порядка оставшихся букв.

Например, если A = "aabab", B = "bbaa" и F = "baba", алгоритм должен вывести "Yes", потому что "aabbaab" имеет A и B в качестве подпоследовательности, но не F.

Есть идеи?

Answer 1

Теперь, когда я немного больше подумал об этой проблеме, я нашел действительно простое и эффективное решение. ;) Эта проблема была действительно намного легче, чем я сначала думал. Это может быть решено за линейное O (| A | + | B |) время без лишних пробелов.

Идея состоит в том, чтобы перебирать символы F и всегда брать максимальную часть A и B в суперпоследовательность, чтобы ее длина не превышала текущий префикс F. Следующий код c ++ проясняет идею:

int i = 0, j = 0;
for (int k = 0; k < F.size()-1; k++) {
    while (i < A.size() && A[i] != F[k]) i++;
    while (j < B.size() && B[j] != F[k]) j++;
    i++; j++;
    if (i >= A.size() && j >= B.size()) {
        cout << "YES";
        return 0;
    }
}
cout << "NO";

Answer 2

Пусть X будет минимальной суперпоследовательностью A и B , если каждая буква X может быть соответствует букве A и / или B по порядку.

Каждая суперпоследовательность A и B является суперпоследовательностью F тогда и только тогда, когда каждая минимальная суперпоследовательность A и B является суперпоследовательностью F .

DFA, который принимает минимальные суперпоследовательности A и B , может быть легко создан с максимум | A | * | B | состояниями с каждым состоянием соответствует паре совместимых позиций в обеих строках. См https://en.wikipedia.org/wiki/Deterministic_finite_automaton и https://en.wikipedia.org/wiki/Powerset_construction

Если есть суперпоследовательность A и B , которая не является суперпоследовательностью F , то через этот DFA есть путь, который не является суперпоследовательность F .

Определите стоимость пути через DFA как длину самого длинного префикса F , который является подпоследовательностью пути, т. Е. Количеством символов, которое вы бы сопоставили с F по дорожке.

Тогда, поскольку DFA является ациклическим, вы можете использовать алгоритм Дейкстры или поиск по принципу «лучший сначала», чтобы найти наименьшую стоимость для достижения каждого состояния. См https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Если любое принимающее государство имеет наименьшую стоимость, которая меньше | F | , то существует суперпоследовательность A и B , которая также не является суперпоследовательность F .

Сложность всей операции O (| A | * | B |)

Самый простой способ реализовать это - использовать матрицу | A | + 1 x | B | + 1 в качестве DFA - точно так же, как та, которую вы используете для Расчет LCS. Каждая ячейка в матрице является состоянием. Заполните ячейки их наименьшей стоимостью, когда они будут обнаружены.