Алгоритм определения возможности замены одной строки на другую путем вставки символов?

Скажем, у меня есть «целевая строка» (или список, не имеет большого значения) некоторой длины N. Для простоты предположим, что есть два и только два возможных символа: «A» и «B». Так, например, возможно, целевая строка — «ABBABB».

Затем мне дается тестовая строка некоторой длины ‹= N (опять же, те же два возможных символа). Я хочу определить, может ли тестовая строка быть преобразована в целевую строку при условии, что единственным допустимым преобразованием является вставка символов.

Например, давайте снова скажем, что цель — ABBABB, а тест — BBB. Тогда да, тест можно превратить в цель; например: BBB -> BBAB -> ABBAB -> ABBABB.

Но если бы тест был БАБА, то его нельзя было бы преобразовать в цель, поскольку цель начинается с А, а тест — нет, и вставка А в тест не сработает, потому что это приведет к тому, что в нем будет больше А. чем у цели.

Очевидно, я мог бы сделать это определение «да» или «нет» грубой силой, перебирая все возможные последовательности вставок символов. Но есть ли более эффективный способ?

Заранее спасибо.


algorithm insertion
person zognortz    schedule 20.04.2012    source источник

Ответы (3)


arrow_upward
7
arrow_downward

На первый взгляд кажется, что простой ответ заключается в том, что если тестовая строка последовательно содержится в целевой строке, то ваш тест проходит успешно.

Что-то типа:

int i = 0;
foreach (char c in target) {
    if (i == test.Length) return true; // Found all test chars
    if (test[i] == c) {
        i++; // found this test char; check for next
        if (i == test.Length) break;
    }
}
return i == test.Length; // Found all test chars
person Mark Brackett    schedule 20.04.2012

arrow_upward
1
arrow_downward

Вы можете использовать динамическое программирование, чтобы решить это. Пусть X будет начальной строкой, а Y будет конечной строкой. Давайте решим противоположную задачу, то есть удалив из Y и посмотрим, сможем ли мы получить X.

F(Y,X) = (if X[0]=Y[0]: F(X[1:],Y[1:] ) or F(Y[1:],X)

Конечное условие: If X='', return True elsif Y='' return False

Обратите внимание, что, как и во всех задачах динамического программирования, вам необходимо вычислить и сохранить F(X[i:],F[j:]) для len(X)*len(Y) различных комбинаций (i,j).

person ElKamina    schedule 20.04.2012

arrow_upward
0
arrow_downward

1) Преобразуйте тестовые/целевые строки в массивы, в которых каждый элемент представляет собой пару, описывающую количество связанных «А» и «В».

например ABBABB ==> { (1,2) (1,2) }; ВВВ ==> {(0,3)}; БАБА ==> { (0,1) (1,1) (1,0) }

2) Определите уровень элемента, содержащий: P1 (a,b) содержит P2 (c,d), если a>=c и b>=d

Определить две операции над двумя элементами P1 (a,b) и P2 (c,d)

объединитьA(P1,P2) ==> (a+c,d);

объединитьB(P1,P2) ==> (a,b+d)

3) Теперь у нас есть абстрактная задача: для заданного тестового массива {T1, T2, ..., Tn} и целевого массива {A1, A2, ... Am} указать, содержит ли целевой массив тестовый массив. Здесь «содержать» можно определить рекурсивно.

Целевой массив содержит тестовый массив, если i. Целевой массив содержит те же или более элементы, что и тестовый массив; II. либо для каждого i из [1,m] Ai содержит Ti

or

mergeA(A1,A2), A3, A4... содержит тестовый массив

or

mergeB(A1,A2), A3, A4... содержит тестовый массив

4) Псевдокод

bool ifContain(Pair[] target, Pair[] test) {
    if (test.length>target.length) return false;
    if (test.length()==1) 
        return (target.A>=test.A && target.B>=test.B);
    return   (ifContain(target[0], test[0]) && ifContain(targe(1,:),test(1,:)))
        || ifContain(Pair(target[0].a,target[0].b+target[1].b)+target(2,:),test)
        || ifContain(Pair(target[0].a+target[1].a+target[1].b)+target(2,:),test);
}
person HelloWorld    schedule 20.04.2012