Бесполезная Задачка

Бесполезная Задачка

Дан массив строк.
Требуется сгенерировать строку наименьшего размера,
в которую бы все строки из массива входили как подстроки.

Например: {aaa, abc, bca} --> aaabca

Миша

Re: Бесполезная Задачка

Mikhail Kimmelman wrote:

Дан массив строк.
Требуется сгенерировать строку наименьшего размера,
в которую бы все строки из массива входили как подстроки.

Например: {aaa, abc, bca} --> aaabca
...


Настоящий Программист внутренним философским чутьем сразу почувствует, что
данная задача соотносится с задачей нахождения Longest Common Subsequence
примерно также, как задача нахождения НОК с задачей нахождения НОД, т.е. одна
легко решается через другую.

И действительно Shortest Common Supersequence

http://en.wikipedia.org/wiki/S... 

легко решается через Longest Common Subsequence

http://en.wikipedia.org/wiki/L... 

--
Best regards,
Andrey Tarasevich

Re: Бесполезная Задачка


"Mikhail Kimmelman" <mikhail.kimmelman@gmail.com> wrote in message
news:fs817j$sb2$1@mamba.crocodile.org...

Дан массив строк.
Требуется сгенерировать строку наименьшего размера,
в которую бы все строки из массива входили как подстроки.

Например: {aaa, abc, bca} --> aaabca


Задачка очень полезная, я ее пользую для нахождения если HTML таг является
валидным, исходный массив это множестов тагов, а результат - минимальная
строка, очень удобно, только я её немного оптимизирую, чтобы часто
встречаюшиеся таги были в начале, в вашем случае надо добавить веса для
строк и сделать усовие чтобы с наибольшим весом стояли в гачале. А вот
решите мне другую задачку, надо найти абрионы максимальной длины в
произвольно строке. Абрионы это такие строки кторые являются зеркадьным
отображением друг друга, например

abbcbbcbba

abbc cbba


Re: Бесполезная Задачка

On Mar 24, 6:18 pm, Andrey Tarasevich <andreytarasev...@hotmail.com>
wrote:



Дан массив строк.
Требуется сгенерировать строку наименьшего размера,
в которую бы все строки из массива входили как подстроки.
Например: {aaa, abc, bca} --> aaabca

Настоящий Программист внутренним философским чутьем сразу почувствует, что
данная задача соотносится с задачей нахождения Longest Common Subsequence
примерно также, как задача нахождения НОК с задачей нахождения НОД, т.е. одна
легко решается через другую.
И действительно Shortest Common Supersequence
http://en.wikipedia.org/wiki/S... 
легко решается через Longest Common Subsequence
http://en.wikipedia.org/wiki/L... 


Это не подстроки.

Kit.

Re: Бесполезная Задачка

Nikita V. Belenki wrote:



И действительно Shortest Common Supersequence
http://en.wikipedia.org/wiki/S... 
легко решается через Longest Common Subsequence
http://en.wikipedia.org/wiki/L... 


Это не подстроки.


Аааа... Да, поспешил. Не подстроки.

--
Best regards,
Andrey Tarasevich

Re: Бесполезная Задачка

"Andrey Tarasevich" <andreytarasevich@hotmail.com> wrote in message
news:fs8n0m$fuh$1@aioe.org...




И действительно Shortest Common Supersequence
http://en.wikipedia.org/wiki/S... 
легко решается через Longest Common Subsequence
http://en.wikipedia.org/wiki/L... 


Это не подстроки.


Аааа... Да, поспешил. Не подстроки.


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

Например, ребро между вершинами "abc" и "bcd" имеет вес 4 ("abcd").

Тогда задача сведется к TSP, т.е. поиску максимального пути обхода
всех вершин в графе.

Миша

Re: Бесполезная Задачка

"Mikhail Kimmelman" <mikhail.kimmelman@gmail.com> wrote in message
news:fsa538$2p9j$1@mamba.crocodile.org...


Тогда задача сведется к TSP, т.е. поиску максимального пути обхода
всех вершин в графе.


минимального конечно же.

Миша

Re: Бесполезная Задачка

On Mar 25, 11:10 am, "Mikhail Kimmelman" <mikhail.kimmel...@gmail.com>
wrote:

"Mikhail Kimmelman" <mikhail.kimmel...@gmail.com> wrote in message

news:fsa538$2p9j$1@mamba.crocodile.org...


Тогда задача сведется к TSP, т.е. поиску максимального пути обхода
всех вершин в графе.


минимального конечно же.

Миша


Ну и какая у вас длина получилась для всех английских слов?

Re: Бесполезная Задачка


"Mikhail Kimmelman" <mikhail.kimmelman@gmail.com> wrote in message
news:fs817j$sb2$1@mamba.crocodile.org...

Дан массив строк.
Требуется сгенерировать строку наименьшего размера,
в которую бы все строки из массива входили как подстроки.
Например: {aaa, abc, bca} --> aaabca


Что делать в случае caa, baa, aad ? Результатов четыре:
caadbaa
baacaad
caabaad
baadcaa

/Alex