|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
03.04.2011, 01:40 | #1 |
Форумчанин
Регистрация: 11.09.2010
Сообщений: 101
|
Одинаковы ли строки? за О(n+m)
Всем вечер добрый
есть вопрос, как можно определить одинаковы ли введенные строки по методу КМП (Кнутта-Морриса-Пратта), и можно ли вообще? СТЛ употреблять нельзя( программа должна работать за О(n+m)). Если префикс функции у строк равны, то это ведь не говорит о равенстве самих строк?..подскажите пожалуйста.
I'm a rebel. [I think positively].
Последний раз редактировалось Guzal; 03.04.2011 в 02:59. |
03.04.2011, 02:35 | #2 |
Software Developer
Участник клуба
Регистрация: 01.03.2011
Сообщений: 1,098
|
Болтовня ничего не стоит. Покажите мне код. (c) Linus Torvalds
Помог ответ? -- Поставьте отзыв. Выражения особой благодарности в рублевом эквиваленте отправлять сюда --> R269634919062 |
03.04.2011, 02:59 | #3 |
Форумчанин
Регистрация: 11.09.2010
Сообщений: 101
|
спасибо
но мне не нужен поиск подстроки в строке, я знаю алгоритм кмп и его реализацию, мне нужна проверка на совпадение строк, их равенство.
I'm a rebel. [I think positively].
|
03.04.2011, 03:01 | #4 |
Software Developer
Участник клуба
Регистрация: 01.03.2011
Сообщений: 1,098
|
да, я уже понял...
Болтовня ничего не стоит. Покажите мне код. (c) Linus Torvalds
Помог ответ? -- Поставьте отзыв. Выражения особой благодарности в рублевом эквиваленте отправлять сюда --> R269634919062 |
03.04.2011, 12:11 | #5 | |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Цитата:
1) А что такое СТЛ ? 2) что такое n и m (если это длины строк, то как могут быть одинаковы строки с различной длиной? поясните, пожалуйста. А то любопытно - а разобраться не могу... |
|
03.04.2011, 12:22 | #6 |
Старожил
Регистрация: 28.01.2009
Сообщений: 21,000
|
судя по STL речь идет о С++.
STL=Standard Template Library Хорошо поставленный вопрос это уже половина ответа. | Каков вопрос, таков ответ.
Программа делает то что написал программист, а не то что он хотел. Функции/утилиты ждут в параметрах то что им надо, а не то что вы хотите. |
03.04.2011, 13:29 | #7 |
Форумчанин
Регистрация: 11.09.2010
Сообщений: 101
|
О(n+m) это О-нотация (Big-Oh-notation) время работы программы, в данном случае она должна работать за время О(n+m) это самое быстрое время, алгоритм КМП вроде работает за такое время..мм..как бы объяснить, если интересно http://en.wikipedia.org/wiki/Big_O_notation
I'm a rebel. [I think positively].
|
03.04.2011, 13:39 | #8 | |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Всем спасибо за ответы!
Цитата:
Что Вы подразумеваете под N и M при записи данной формулы? поясню, имхо, если это длины строк 1 и 2 ТО: 1) N=M (всегда, иначе строки не могут быть равны) 2) их равенство определяется за время O(N) |
|
03.04.2011, 14:05 | #9 | |
Форумчанин
Регистрация: 11.09.2010
Сообщений: 101
|
Цитата:
если не заморачиваться надо сложными алгоритмами то можно ведь.. Код:
I'm a rebel. [I think positively].
|
|
03.04.2011, 15:00 | #10 | |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Цитата:
|
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Создание пустой строки и копирование в неё содержимое предыдущей строки | Gvaridos | Microsoft Office Excel | 2 | 29.10.2010 13:33 |
Определять максимальную длину той части строки s, которая не содержит символы из строки s1. | Александе еть я | Общие вопросы C/C++ | 5 | 13.04.2010 20:54 |
Создать матрицу A[1..N,1..M]. Найти две строки, в которых элементы одинаковы, но могут стоять в различной | Bapr | Помощь студентам | 7 | 11.12.2009 17:44 |
Перенести символа с начала строки в место перед запятой этой же строки. | Zhiltsov | Microsoft Office Excel | 4 | 05.06.2009 13:10 |
Команды у процов одинаковы | mogul82 | Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM | 1 | 23.11.2008 21:25 |