Developing.ru

Люди! Кто-нибудь сталкивался с подобной задачей?
Есть наборы взаимозаменяемых вариантов, например:
1. A,AB,CDE
2. X,YZ
3. G,F,FH

Из них генерируются сочетания (берется по 1 варианту из каждого набора):
AXG
AXF
AXFH
AYZG
AYZF
..
CDEYZFH

В условии дан список получившихся строк, надо восстановить
исходные варианты
1. A,AB,CDE
2. X,YZ
3. G,F,FH

Нет у кого ссылок на материалы? Или есть алгоритм, решающий данную задачу? Подскажите пожалуйста..

В условии только строки? Количество вариантов неизвестно? В каждую строку входят все варианты? Известна ли максимальная длина подстроки?

Ах, да, задается кол-во наборов. И все. Надо восстановить наборы

Наверное, нужно искать варианты по частоте вхождения подстрок в наборы. Например, берём самый короткий набор и считаем его вхождение в другие наборы, укорачиваем его на 1 символ справа и опять считаем и так до получения максимума. Конечно, если во входных наборах представлены все комбинации.

Берем начало списка
AXG
AXF
Находим самую длинную повторяющуюся строку - АХ. Стало быть, G, F и дальше FH - элементы последнего набора. Идем дальше по строкам, пока начало не будет отлично от АХ. Это будет А - значит, Х принадлежит к предпоследнему набору, так что идем дальше и считываем по очереди все символы предпоследнего набора. И так пока не разберем всю строку.