|
|
|
Наибольшая общая строка
|
|||
|---|---|---|---|
|
#18+
Здравствуйте! Есть следующая задача. Дано n<10 строк длинна которых меньше 10000 символов каждая. Нужно найти наибольшую общую подстроку. Задача сама по себе простая, но сложность в том что по времени она должна выполняться менее чем за 1,5 секунды. Я использовал следующий алгоритм: Искал наикратчайшую строку, делал из нее подстроки длинной меньше на 1, на 2 и т.д. и каждую подстроку сразу после создания проверял на то, чтобы она находилась в оставшихся исходных строках. Если это выполняется то строка выводится и программа закрывается. Однако при длине входящих строк от 7000 время выполнения больше чем 1,5 сек. Кто может, предложите какой-нибудь быстрый алгоритм, ну или способ ускорить программу. Код прилагается : Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. Заранее спасибо! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2012, 19:17:24 |
|
||
|
Наибольшая общая строка
|
|||
|---|---|---|---|
|
#18+
grasoff.net, Недурно... Спасибо посмотрю:) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2012, 23:35:43 |
|
||
|
Наибольшая общая строка
|
|||
|---|---|---|---|
|
#18+
ОК. А тогда такой вопрос: там алгоритм для 2ух строк, а как мне его использовать для n строк? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.04.2012, 12:18:13 |
|
||
|
Наибольшая общая строка
|
|||
|---|---|---|---|
|
#18+
dirty_valera, а общая построка - это что? - входит во все исходные строки - входит в не менее чем в 2 исходные строки - встречается не менее чем в 2х местах, может быть и в одной исходной строке какой алфавит используется? для символа надо 2 байта (char) или достаточно одного? строки содержат текст на естественном языке или же это случайный набор символов? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.04.2012, 19:29:40 |
|
||
|
Наибольшая общая строка
|
|||
|---|---|---|---|
|
#18+
dirty_valera, какая-то постановка - синтетическая. Здесь можно очень сильно выиграть если заранее знать что строки состоят из слов (текст) и индексируя цепочки слов сильно сокращать время поиска. Если это url-s - то соотвествтенно отбросить ненужные проверки и искать совпадения только с начала (т.к. url по другому не substring-гуестя). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.05.2012, 14:57:12 |
|
||
|
|

start [/forum/topic.php?fid=59&tid=2131882]: |
0ms |
get settings: |
7ms |
get forum list: |
16ms |
check forum access: |
6ms |
check topic access: |
6ms |
track hit: |
52ms |
get topic data: |
15ms |
get forum data: |
3ms |
get page messages: |
57ms |
get tp. blocked users: |
2ms |
| others: | 336ms |
| total: | 500ms |

| 0 / 0 |
