удалить фрагменты в предложении [пазл]

Question

Вопрос:

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

Пример:

Input ::

s1 = "Идет дождь, и я хочу поехать домой.";

s2 = "Идет дождь, и я хочу кататься на лыжах.";

s3 = "Жарко, и я хочу плавать.";

Выход ::

s1 = "Идет дождь, едем домой.";

s2 = "Идет дождь, катаюсь на лыжах.";

s3 = "Идет жаркое плавание.";

Удален фрагмент =" и я хочу "

Программа снова будет проверена большими файлами.Эффективность будет приниматься во внимание.

Допущения: Игнорировать заглавные буквы, знаки пунктуации.но сохранить в выходных данных.

Примечание: Позаботьтесь о таких случаях, как

aaaaabcbcbcbc, где удаление приведет к созданию дополнительных фрагментов.

Мое решение: (который, я думаю, не самый эффективный)

1. Хэш трех фраз слова в int и сохранить их в массиве, для всех строк.сводится к массиву чисел типа

   1 2 3 4 5
   3 5 7 9 8
   9 3 1 79
   

Проблема сводится к пересечению массивов.

сортировка массивов.(k * nlogn)

сохранить k указателей.если все равные совпадения найдены.иначе приращение указателя указывает на наименьшее значение.Решить для Примечание выше.Я думал о том, чтобы выполнить отложенное удаление, то есть пометить фразы для удаления и удалить в конце.

Есть ли случаи, когда моё решение может не работать?Можем ли мы оптимизировать мое решение / найти лучшее решение?

Answer 1

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

Теперь у вас есть проблема, связанная с удалением самой длинной последовательности букв, которая появляется в всех словах данного списка.Таким образом, вы должны вычислить самую длинную общую подстроку для набора «слов».Вы найдете его, используя обобщенное суффиксное дерево , так как это самый эффективный алгоритм.Это должно сработать, и я считаю, что имеет наилучшую сложность.

Answer 2

Первый шаг, как уже предлагал izomorphius:

Замените каждое слово одной "буквой" в большом алфавите (т.е. каким-то образом хешируйте миры), удалите пробелы и знаки препинания.

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

Просто переберите первую строку и поместите все ее 3-подстроки в хеш-таблицу как ключи со значениями, равными 1. Затем переберитевторая строка и для каждой 3-подстроки x, если x находится в хеш-таблице и его значение равно 1, затем установите значение 2. Затем выполните итерацию по третьей строке и для каждой 3-подстроки x, если x находится в хеш-таблицеtable и его значение равно 2, затем установите значение 3. ... и так далее.В конце ключи, имеющие значение k, являются общими 3-подстроками.

Теперь просто повторите итерацию по всем строкам и удалите эти 3-подстроки, которые являются общими.

Answer 3

Мое решение будет что-то вроде,

F = all fragments with length > 3 shared by the first 2 lines, avoid overlaps
for each line from the 3rd line and up
    remove fragments in F which do not exist in line, or cause overlaps

return sentences with fragments in F removed

Я предполагаю, что поиск / сопоставление фрагментов в предложениях может быть сделано с помощью некоторого известного алгоритма. но с точки зрения сложности времени для n строк это O (n)