Восстановить пропущенную пробел строку в O (n^2)

Я хочу проверить правильность моего алгоритма.Восстановить пропущенную пробел строку в O (n^2)

Получая строку из п символов со всем белым пространством опущены,

Ex: "itwasthebestoftimes"

Дайте алгоритм динамического программирования, который определяет, если строка может быть разбита на действительную последовательность слов, и восстановить действительную строку пробелы, в O (n).

Моя идея:

Сначала найдите все подстроки строки (O (п)), и для каждой подстроки карты ее положение в пространстве и длины, как интервал.

Ex: "it was the best" 
     [] [-] [-] [--] 
     [---] []  
      []

(Пространства добавлены, чтобы упростить просмотр).

В приведенном выше примере, «это» является действительным, и получает значение интервала из 2, «был» получает 3 и т.д. Строка «ТВАС» также справедливо, и получает значение 4.

Затем это уменьшено до задачи мини-макс, чтобы найти максимальную длину, не перекрывающуюся в наборе интервалов. Так как допустимая строка должна содержать все буквы, то ответом будет максимальный интервал между перекрывающимися интервалами, и нахождение этого занимает Theta (n * log (n)).

Поэтому решение будет принимать O (п + п * журнала (п)) = O (п)

ли мое мышление правильно?

источник

2017-02-22 mrybak3

Как вы выбираете, какой подстроки идет в какой строке? Когда вы пытаетесь поместить новую подстроку в нижнюю строку, потому что она перекрывается, откуда вы знаете - может быть, путем перестановки существующих подстрок в строках вы могли бы подгонять новую подстроку? – avysk

Жаль об этом, отредактирован. Не имеет значения, в какую «строку» входит подстрока, она произвольна для минимаксного решателя. Все, что имеет значение, проверяет, есть ли столкновение или нет, которое задается координатами интервала.Строки только там, чтобы облегчить визуальное представление – mrybak3

На самом деле, есть ли у вас указатель на алгоритмы O (n log n) для нахождения непересекающегося подмножества интервалов максимальной общей длины? Это легко сделать в O (n^2) (с тем же динамическим программированием), но я не вижу сразу (и не могу найти никаких материалов после краткого поиска), как это сделать в O (n log n). Вы уверены, что не смешиваете эту проблему с нахождением максимального * числа * непересекающихся интервалов, а не максимальной * общей длины *? Для максимального числа жадный алгоритм - это O (n log n). – avysk

Ваше мышление прекрасное (если вы знаете решение O (n log n) проблемы нахождения максимального набора неперекрывающихся интервалов) и что вы знаете способ найти интервалы слов в O (n^2) время. Однако, я думаю, проблема проще, чем вы ее делаете.

Создать массив W[0...n]. W[i] будет 0, если нет способа вырезать строку с i и далее в слова, и в противном случае она сохранит длину слова, которое начнет действительное разделение строк.

Тогда:

W[i] = min(j such that W[i:j] is a word, and i+j = n or W[i+j]>0) 
     or 0 if there's no such j.

Если вы держите свой словарь в синтаксического дерева, вы можете вычислить W[i] в O (н-я) раз предполагает, что вы уже вычислен W[i+1] к W[n-1]. Это означает, что вы можете вычислить все W в O (n^2) времени. Или, если максимальная длина слова в вашем словаре равна k, вы можете сделать это в O (nk) раз.

После того, как вы вычисляться все W, вся строка может быть разрезана на слова, если и только если W[0] не 0.

источник

2017-02-22 21:50:24

Восстановить пропущенную пробел строку в O (n^2)

ответ

Смежные вопросы