Текст и последовательность операций
Короче, есть такая задачка...
Дана текстовая строка X состоящая из букв некого алфавита. Над этой строкой можно производить следующие операции:
1.Замена участка текста с позиции P и длинной L на произвольный текст той же длинны (частный случай – замена одной буквы).
2.Вставка в позицию P произвольного текста длинной L.
3.Удаление куска текста длинной L в позиции P.
4.Инверсия текста в позиции P и длинной L (например: ABCDEF может превратиться в ADCBEF)
5.Дубликация текста в позиции P и длинной L в новую позицию P1 (например: ABCDEF – ABCDEABCF)
В результате определенной последовательности действий получается новая строка Y.
Как решить прямую задачу (т.е. дана X и последовательность действий) понятно! А вот как решить обратную задачу (т.е. дана X и Y, надо найти все возможные последовательности действий, которые привели к преобразованию X в Y)???
Такая задача вообще решена??? Что можно почитать по этой теме? В какую сторону капать?
Дана текстовая строка X состоящая из букв некого алфавита. Над этой строкой можно производить следующие операции:
1.Замена участка текста с позиции P и длинной L на произвольный текст той же длинны (частный случай – замена одной буквы).
2.Вставка в позицию P произвольного текста длинной L.
3.Удаление куска текста длинной L в позиции P.
4.Инверсия текста в позиции P и длинной L (например: ABCDEF может превратиться в ADCBEF)
5.Дубликация текста в позиции P и длинной L в новую позицию P1 (например: ABCDEF – ABCDEABCF)
В результате определенной последовательности действий получается новая строка Y.
Как решить прямую задачу (т.е. дана X и последовательность действий) понятно! А вот как решить обратную задачу (т.е. дана X и Y, надо найти все возможные последовательности действий, которые привели к преобразованию X в Y)???
Такая задача вообще решена??? Что можно почитать по этой теме? В какую сторону капать?
Цитата:
Originally posted by sonjia
Короче, есть такая задачка...
Дана текстовая строка X состоящая из букв некого алфавита. Над этой строкой можно производить следующие операции:
1.Замена участка текста с позиции P и длинной L на произвольный текст той же длинны (частный случай – замена одной буквы).
2.Вставка в позицию P произвольного текста длинной L.
3.Удаление куска текста длинной L в позиции P.
4.Инверсия текста в позиции P и длинной L (например: ABCDEF может превратиться в ADCBEF)
5.Дубликация текста в позиции P и длинной L в новую позицию P1 (например: ABCDEF – ABCDEABCF)
В результате определенной последовательности действий получается новая строка Y.
Как решить прямую задачу (т.е. дана X и последовательность действий) понятно! А вот как решить обратную задачу (т.е. дана X и Y, надо найти все возможные последовательности действий, которые привели к преобразованию X в Y)???
Такая задача вообще решена??? Что можно почитать по этой теме? В какую сторону капать?
Короче, есть такая задачка...
Дана текстовая строка X состоящая из букв некого алфавита. Над этой строкой можно производить следующие операции:
1.Замена участка текста с позиции P и длинной L на произвольный текст той же длинны (частный случай – замена одной буквы).
2.Вставка в позицию P произвольного текста длинной L.
3.Удаление куска текста длинной L в позиции P.
4.Инверсия текста в позиции P и длинной L (например: ABCDEF может превратиться в ADCBEF)
5.Дубликация текста в позиции P и длинной L в новую позицию P1 (например: ABCDEF – ABCDEABCF)
В результате определенной последовательности действий получается новая строка Y.
Как решить прямую задачу (т.е. дана X и последовательность действий) понятно! А вот как решить обратную задачу (т.е. дана X и Y, надо найти все возможные последовательности действий, которые привели к преобразованию X в Y)???
Такая задача вообще решена??? Что можно почитать по этой теме? В какую сторону капать?
Последовательность действий будет бысто стемиться к бесконечности, т.к. чтобы преобразовать A->B можно заменить символ сразу, а можно A->C->G->S->A->V->B
Цитата:
Originally posted by Archie
Последовательность действий будет бысто стемиться к бесконечности, т.к. чтобы преобразовать A->B можно заменить символ сразу, а можно A->C->G->S->A->V->B
Последовательность действий будет бысто стемиться к бесконечности, т.к. чтобы преобразовать A->B можно заменить символ сразу, а можно A->C->G->S->A->V->B
Там вводятся ограничения, что бы не было такой и подобных ситуаций.
Цитата:
Originally posted by sonjia
Короче, есть такая задачка...
Короче, есть такая задачка...
Сперва нужно определить наиболее длинные общие подпоследовательности двух строк. Напр. AABCCDD СBCFGCCCDEED, тогда
С[color=red]ABC[/color][color=darkblue]CD[/color]H[color=green]D [/color]
AAA[color=red]ABC[/color]FGCC[color=darkblue]CD[/color]EE[color=green]D[/color]
И после этого можно двигаться дальше.
В книге. Дж.Бакнелл-"Фундаментальные алгоритмы и структуры данных в Delphi" есть программа выделяющая подстроки.
Более точная постановка задачи...
Дана текстовая строка X состоящая из букв некого алфавита. Над этой строкой можно производить следующие операции редактирования:
1. Замена подстроки с позиции P и длинной L на произвольную подстроку той же длинны.
2. Вставка в позицию P произвольного текста длинной L.
3. Удаление подстроки длинной L в позиции P.
4. Инверсия текста в позиции P и длинной L.
5. Дубликация подстроки в позиции P и длинной L в новую позицию P1.
В результате определенной последовательности действий получается новая строка Y.
Каждая операция имеет свою цену. Эта цена зависит от длинны подстроки (L), ее позиции (P) и от ряда других факторов (все это задается перед началом работы).
Необходимо найти все последовательности операций редактирования с суммой их цен:
1. находящийся в некотором заданном интервале.
2. если такой не задан, то искать с минимальной суммой цен (но эта сумма цен должна быть больше или равна некоторого заданного минимального значения, частный случай – минимальное значение равно 0).
Дана текстовая строка X состоящая из букв некого алфавита. Над этой строкой можно производить следующие операции редактирования:
1. Замена подстроки с позиции P и длинной L на произвольную подстроку той же длинны.
2. Вставка в позицию P произвольного текста длинной L.
3. Удаление подстроки длинной L в позиции P.
4. Инверсия текста в позиции P и длинной L.
5. Дубликация подстроки в позиции P и длинной L в новую позицию P1.
В результате определенной последовательности действий получается новая строка Y.
Каждая операция имеет свою цену. Эта цена зависит от длинны подстроки (L), ее позиции (P) и от ряда других факторов (все это задается перед началом работы).
Необходимо найти все последовательности операций редактирования с суммой их цен:
1. находящийся в некотором заданном интервале.
2. если такой не задан, то искать с минимальной суммой цен (но эта сумма цен должна быть больше или равна некоторого заданного минимального значения, частный случай – минимальное значение равно 0).