Оптимальное решение для неперекрывающихся последовательностей максимального выигрыша

Question

При разработке части симулятора я столкнулся со следующей проблемой. Рассмотрим строку длиной N и M подстрок этой строки с неотрицательной оценкой, присвоенной каждой из них. Особый интерес представляют наборы подстрок, отвечающие следующим требованиям:

1. Они не перекрываются.
2. Их общий балл (по сумме для простоты) максимален.
3. Они охватывают всю строку.

Я понимаю, что наивное грубое решение имеет сложность O (M * N ^ 2). Хотя реализация этого алгоритма, вероятно, не сильно повлияет на производительность всего проекта (нигде рядом с критическим путем, не может быть предварительно вычислена и т. Д.), На самом деле он мне не подходит. Я хотел бы знать, есть ли лучшие решения этой проблемы и если да, то какие они? Указатели на соответствующий код всегда приветствуются, но подойдет и описание алгоритма.

Answer 1

Это можно рассматривать как поиск самого длинного пути через DAG. Каждая позиция в строке является узлом, а каждое совпадение подстроки является ребром. Вы можете с помощью индукции легко доказать, что для любого узла на оптимальном пути конкатенация оптимального пути от начала к этому узлу и от этого узла до конца совпадает с оптимальным путем. Благодаря этому вы можете просто отслеживать оптимальные пути для каждого узла и убедиться, что вы посетили все ребра, которые заканчиваются в узле, прежде чем начинать рассматривать пути, содержащие его.

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

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

Answer 2

Не ясно, даны ли подстроки M в виде последовательности символов или индексов во входной строке, но проблема не сильно из-за этого.

Пусть у нас есть входная строка S длиной N и M входных строк Tj. Пусть Lj - длина Tj, а Pj - оценка, заданная для строки Sj. Мы говорим, что строка

Это называется Динамическое программирование или DP. Вы сохраняете массив res с длиной N, где i-й элемент представляет счет, который можно получить, если он имеет только подстроку, начиная с i-го элемента (например, если input имеет значение «abcd», то res [ 2] будет представлять лучший результат, который вы можете получить из "cd").

Затем вы перебираете этот массив от конца к началу и проверяете, можете ли вы начать строку Sj с i-го символа. Если вы можете, то результат (res [i + Lj] + Pj) явно достижим. Итерируя по всем Sj, res [i] = max (res [i + Lj] + Pj) для всех Sj, которые могут быть применены к i-му символу.

res [0] будет вашим последним ответом.

Answer 3

Входы:

N, the number of chars in a string
e[0..N-1]: (b,c) an element of set e[a] means [a,b) is a substring with score c.  

(Если возможны все подстроки, то у вас может быть только c (a, b).)

Например, [1,2) мы имеем в виду подстроку, охватывающую 2-ю букву строки (полуоткрытый интервал).

(пустые подстроки не разрешены; если бы они были, то вы могли бы обрабатывать их должным образом только в том случае, если вы позволяете их "брать" не более k раз)

Выходы:

s[i] is the score of the best substring covering of [0,i)
a[i]: [a[i],i) is the last substring used to cover [0,i); else NULL

Алгоритм - O (N ^ 2), если интервалы e не редки; O (N + E) где e - общее количество разрешенных интервалов. Это эффективно находит лучший путь через ациклический граф:

for i = 0 to N:
    a[i] <- NULL
    s[i] <- 0
a[0] <- 0
for i = 0 to N-1
    if a[i] != NULL
        for (b,c) in e[i]:
            sib <- s[i]+c
            if sib>s[b]:
                a[b] <- i
                s[b] <- sib

Чтобы получить наилучшие тройки покрытия (a, b, c), где стоимость [a, b) равна c:

i <- N
if (a[i]==NULL):
    error "no covering"
while (a[i]!=0):
    from <- a[i]
    yield (from,i,s[i]-s[from]
    i <- from

Конечно, вы можете сохранить пару (sib, c) в s [b] и сохранить вычитание.

Answer 4

O (N + M) решение:

Set f[1..N]=-1
Set f[0]=0
for a = 0 to N-1
    if f[a] >= 0
        For each substring beginning at a
            Let b be the last index of the substring, and c its score
            If f[a]+c > f[b+1]
                Set f[b+1] = f[a]+c
                Set g[b+1] = [substring number]
Now f[N] contains the answer, or -1 if no set of substrings spans the string.
To get the substrings:
b = N
while b > 0
    Get substring number from g[N]
    Output substring number
    b = b - (length of substring)