Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 03.04.2011, 01:40   #1
Guzal
Форумчанин
 
Аватар для Guzal
 
Регистрация: 11.09.2010
Сообщений: 101
По умолчанию Одинаковы ли строки? за О(n+m)

Всем вечер добрый
есть вопрос, как можно определить одинаковы ли введенные строки по методу КМП (Кнутта-Морриса-Пратта), и можно ли вообще? СТЛ употреблять нельзя( программа должна работать за О(n+m)).
Если префикс функции у строк равны, то это ведь не говорит о равенстве самих строк?..подскажите пожалуйста.
I'm a rebel. [I think positively].

Последний раз редактировалось Guzal; 03.04.2011 в 02:59.
Guzal вне форума Ответить с цитированием
Старый 03.04.2011, 02:35   #2
Mandrivnyk
Software Developer
Участник клуба
 
Аватар для Mandrivnyk
 
Регистрация: 01.03.2011
Сообщений: 1,098
По умолчанию

Примеры реализации алгоритма Кнута - Морриса - Пратта
Болтовня ничего не стоит. Покажите мне код. (c) Linus Torvalds
Помог ответ? -- Поставьте отзыв.
Выражения особой благодарности в рублевом эквиваленте отправлять сюда --> R269634919062
Mandrivnyk вне форума Ответить с цитированием
Старый 03.04.2011, 02:59   #3
Guzal
Форумчанин
 
Аватар для Guzal
 
Регистрация: 11.09.2010
Сообщений: 101
По умолчанию

спасибо
но мне не нужен поиск подстроки в строке, я знаю алгоритм кмп и его реализацию, мне нужна проверка на совпадение строк, их равенство.
I'm a rebel. [I think positively].
Guzal вне форума Ответить с цитированием
Старый 03.04.2011, 03:01   #4
Mandrivnyk
Software Developer
Участник клуба
 
Аватар для Mandrivnyk
 
Регистрация: 01.03.2011
Сообщений: 1,098
По умолчанию

Цитата:
Сообщение от Guzal Посмотреть сообщение
спасибо
но мне не нужен поиск подстроки в строке, я знаю алгоритм кмп и его реализацию, мне нужна проверка на совпадение строк, их равенство.
да, я уже понял...
Болтовня ничего не стоит. Покажите мне код. (c) Linus Torvalds
Помог ответ? -- Поставьте отзыв.
Выражения особой благодарности в рублевом эквиваленте отправлять сюда --> R269634919062
Mandrivnyk вне форума Ответить с цитированием
Старый 03.04.2011, 12:11   #5
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
СТЛ употреблять нельзя( программа должна работать за О(n+m)).
простите меня на "дремучесть"..
1) А что такое СТЛ ?
2) что такое n и m (если это длины строк, то как могут быть одинаковы строки с различной длиной?

поясните, пожалуйста.
А то любопытно - а разобраться не могу...
Serge_Bliznykov вне форума Ответить с цитированием
Старый 03.04.2011, 12:22   #6
Пепел Феникса
Старожил
 
Аватар для Пепел Феникса
 
Регистрация: 28.01.2009
Сообщений: 21,000
По умолчанию

судя по STL речь идет о С++.
STL=Standard Template Library
Хорошо поставленный вопрос это уже половина ответа. | Каков вопрос, таков ответ.
Программа делает то что написал программист, а не то что он хотел.
Функции/утилиты ждут в параметрах то что им надо, а не то что вы хотите.
Пепел Феникса вне форума Ответить с цитированием
Старый 03.04.2011, 13:29   #7
Guzal
Форумчанин
 
Аватар для Guzal
 
Регистрация: 11.09.2010
Сообщений: 101
По умолчанию

Цитата:
Сообщение от Пепел Феникса Посмотреть сообщение
речь идет о С++.
STL=Standard Template Library
О(n+m) это О-нотация (Big-Oh-notation) время работы программы, в данном случае она должна работать за время О(n+m) это самое быстрое время, алгоритм КМП вроде работает за такое время..мм..как бы объяснить, если интересно http://en.wikipedia.org/wiki/Big_O_notation
I'm a rebel. [I think positively].
Guzal вне форума Ответить с цитированием
Старый 03.04.2011, 13:39   #8
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Всем спасибо за ответы!

Цитата:
О(n+m) это О-нотация (Big-Oh-notation) время работы программы,
я знаю, что это такое.
Что Вы подразумеваете под N и M при записи данной формулы?

поясню, имхо, если это длины строк 1 и 2 ТО:
1) N=M (всегда, иначе строки не могут быть равны)
2) их равенство определяется за время O(N)
Serge_Bliznykov вне форума Ответить с цитированием
Старый 03.04.2011, 14:05   #9
Guzal
Форумчанин
 
Аватар для Guzal
 
Регистрация: 11.09.2010
Сообщений: 101
По умолчанию

Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение
Всем спасибо за ответы!


я знаю, что это такое.
Что Вы подразумеваете под N и M при записи данной формулы?

поясню, имхо, если это длины строк 1 и 2 ТО:
1) N=M (всегда, иначе строки не могут быть равны)
2) их равенство определяется за время O(N)
да, я заметила сейчас, но в лабораторной написано за О(н+м)
если не заморачиваться надо сложными алгоритмами то можно ведь..


Код:
#include <iostream>
using namespace std;

	int main()
	{
	    string s, s1;
	    cin>>s>>s1;
	     bool match;
	    for(int i=0; i<s.length(); i++)
	    {
	    	if(s[i]==s1[i])
	    		 match=true;
	    		 else match=false;

	    }
	
	    if(match)
	    	cout<<"match";
	    		else 
	    			cout<<"no match";
	return 0;
	}
должно работать за О(н) даже для больших н
I'm a rebel. [I think positively].
Guzal вне форума Ответить с цитированием
Старый 03.04.2011, 15:00   #10
LeBron
Форумчанин
 
Регистрация: 10.10.2009
Сообщений: 680
По умолчанию

Цитата:
Сообщение от Guzal Посмотреть сообщение
да, я заметила сейчас, но в лабораторной написано за О(н+м)
если не заморачиваться надо сложными алгоритмами то можно ведь..


Код:
#include <iostream>
using namespace std;

	int main()
	{
	    string s, s1;
	    cin>>s>>s1;
	     bool match;
	    for(int i=0; i<s.length(); i++)
	    {
	    	if(s[i]==s1[i])
	    		 match=true;
	    		 else match=false;

	    }
	
	    if(match)
	    	cout<<"match";
	    		else 
	    			cout<<"no match";
	return 0;
	}
должно работать за О(н) даже для больших н
В зависимости от того, под какой именно средой С++ компилить... Может работать, может и не работать) Приколы будут из-за обращения к элементу строки, которого не существует. Ну а если первая строка короче - тогда для "a" и "аа" ответ будет "равны". Сначала надо сравнивать длины строк, а уж если равны - сравнивать посимвольно. Разве что в условии сказано, что они всегда одинаковой длины.
LeBron вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Создание пустой строки и копирование в неё содержимое предыдущей строки 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