Читайте также:
|
Опубликовано 31.01.2013 автором admin
Доброго времени суток всем 
Тема сегодняшней статьи будет о том, как найти число вхождений подстроки в строку. Ну, а в частности, делать мы это будем с помощью нахождения z-функции строки.
Конечно существует очень много алгоритмов, которые могут помочь нам в этом, но сегодня мы рассмотрим именно этот.
Итак, для начала определимся что такое z-функция.
Допустим, мы имеет строку s и массив z. В каждой i-той ячейке массива мы будем хранить максимальное количество символов (число), которые полностью совпадают с символами находящимися вначале строки. Для более понятного объяснения, вот Вам наглядное пособие).
ОБЪЯСНЕНИЕ
Как Вы видите, здесь мы имеем строку abacaba. Теперь разберем массив. В первой ячейке мы пишем 0, потому что для нее не нужно находить какое-либо значение, так как мы уже знаем что оно будет максимально.
Далее, мы имеем символ ‘b’, который не совпадает даже с первой буквой строки, и поэтому пишем ’0′. Третьей буквой (соответственно в массиве 2 индекс), мы видим букву ‘a’, и так как она совпадает с первой буквой строки увеличиваем значение на 1. Дальше идет ‘c’, и в 3 ячейке массива мы пишем ноль.
Следующая буква снова ‘a’, и мы увеличиваем значение на 1. Сразу за ней мы видим ‘b’, и соответственно УЖЕ ДВА СИМВОЛА совпадают с начальными двумя. Увеличиваем 4 ячейку еще на 1. За ней идет снова ‘a’, и мы снова видим что она совпадает со следующей буквой. Также увеличиваем на 1. Вообщем выходит 3. И так далее.
КОД АЛГОРИТМА
Теперь рассмотрим саму функцию, реализованную на С++, которая работает за асимптотику О(n*n), то есть квадрат от длины строки.
Это очень простой код:
| # include <iostream> using namespace std; int zf[100]; int main() { string s; cin>>s; for(int i=1; i<s.size(); ++i) { while(s[zf[i]]==s[zf[i]+i]) zf[i]++; } for(int i=0; i<s.size(); ++i) cout<<zf[i]; system("pause"); } |
Здесь мы для каждой ячейки сравниваем символы и увеличиваем ответ для zf[i], пока не найдем НЕсовпадение или не дойдем до конца строки.
Этот алгоритм работает не так быстро, так что теперь рассмотрим наиболее быстрый метод решения этой задачи.
КОД ЭФФЕКТИВНОГО НАХОЖДЕНИЯ Z-ФУНКЦИИ
В этом алгоритме, мы будем максимально использовать информацию, которую уже нашли до того, как дошли до i-той ячейки.
Этот код уже немного побольше, но все заключается в том, что если мы ищем ответ для какой-то подстроки, которая меньше той, для которой мы искали ответ раньше, мы можем воспользоваться информацией, которую получили заранее.
Вот сам код:
| # include <iostream> using namespace std; int zf[100]; int main() { string s; cin>>s; //Здесь мы будем хранить //координаты самого длинного //отрезка, который совпадает с //началом нашей строки int r=-1,l=-1; //Запускаем цикл для прохождения по строке for(int i=1; i<s.size(); ++i) { //Проверяем, если ячейка для //которой мы ищем ответ //находится в отрезке между //l и r if(i<=r) { /* Это означает, что у нас уже есть такая же ячейка для которой мы искали ответ */ zf[i]=min(r-i+1,zf[i-l]); } //Теперь пользуемся тривиальным алгоритмом while(s[zf[i]]==s[zf[i]+i]) zf[i]++; //И обновляем границы нашей подстроки if(i+z[i]-1>r) { l=i; r=i+z[i]-1; } } //Выводим ответ на экран for(int i=0; i<s.size(); ++i) cout<<zf[i]; system("pause"); } |
Ну что ж, теперь подумаем, как можно использовать алгоритм нахождения z-функции для нахождения количества вхождения подстроки?
Для этого, нам стоит просто поместить подстроку которую мы ищем вперед, и разделить ее каким-либо знаком. Знаю что не понятно;))) поэтому покажу как)))
Допустим, есть строка abcqweabcqwe и нам нужно найти в ней строку abc.
Для этого соединим все в одну строчку вот так: abc#abcqweabcqwe
Теперь мы можем просто запустить z-функцию, и она найдет нам такой ответ:
Как вы видите, здесь она нашла все вхождения строк, которые совпадают с началом строки (до символа #). Значит остается только пройти по массиву, и посчитать сколько раз у нас встречается цифра которая равна длине нашей строки.
Ну в общем, в конце у меня вышел такой код: (может кому пригодится )
| # include <iostream> using namespace std; int zf[100]; int main() { string h,f; cin>>h>>f; string s=f+"#"+h; int r=-1,l=-1; for(int i=1; i<s.size(); ++i) { if(i<=r) { zf[i]=min(r-i+1,zf[i-l]); } while(s[zf[i]]==s[zf[i]+i]) zf[i]++; if(i+zf[i]-1>r) { l=i; r=i+zf[i]-1; } } cout<<s<<endl; for(int i=0; i<s.size(); ++i) cout<<zf[i]; cout<<endl; system("pause"); } |
Спасибо за внимание, скоро напишу еще что-нибудь из алгоритмов на С++. Кстати, кому что надо, ну там какие статьи или информация пишите в комменты, как прочту так напишу статейку.
Быстрое возведение числа в степень на С++
Опубликовано 29.01.2013 автором admin
Всем привет! Очередная статья по алгоритмам языка С++, и сегодня мы будем учиться писать функцию, которая возводит число в степень за log(степень).
Если вы еще не читали что такое функция на С++ или как писать программы на С++, то советуем Вам посетить эти статьи(ну по возможности и прочитать )
Функции в С++
Что такое С++
Итак, начнем нашу лекцию). Для начала хочу рассказать о простых математических формулах, который будут использованы в нашей функции для быстрого возведения числа в степень.
Как Вы знаете, если у нас есть число A в степени X, то есть AX, мы можем написать это как (Az)y, где z*y=x.
Соответственно, если z будет просто 2, нам потребуется лишь возвести число в квадрат, а y поделить на 2.
Но также стоит учитывать такой случай, когда Х может быть нечетным числом. Тогда нам нужно просто возвести А в квадрат, и после чего продолжать наши действия деления X (Так как С++ при делении int`a будет оставлять только целую часть).
Теперь когда принцип работы алгоритма нам известен, осталось показать Вам код и все встанет на свои места
| # include <iostream> using namespace std; int bin_pow(int a, int b) { int res = 1; while(b) { if(b % 2 == 1) { res *=a; } b/=2; a*=a; } return res; } int main() { int a,b; cout<<bin_pow(a,b); system("pause"); } |
Теперь немного разберем код. У нас есть функция под названием bin_pow, которая принимает два параметра, переменные А и B.
После этого, мы проверяем условие того, что B нечетное, и если оно выполнено, возводим ответ в квадрат.
Теперь просто продолжаем наши действия с делением степени и возведением числа А в квадрат.
После того, как B, становится единицей, мы останавливаем цикл и возвращаем ответ.
Надеюсь, алгоритм работы был понятен, спасибо за внимание!
Изменение позиции курсора. С++
Опубликовано 05.12.2012 автором admin
Всем привет! С вами я, Руслан, администратор сообщества. Сегодня хотел рассказать вам о том, как когда-то писал маленькие «программы-приколы» на с++.
Итак, речь пойдет о так сказать бешеном курсоре, а именно о изменении позиции курсора на с++. Для начала хочу сказать, что для того чтобы переместить курсор на с++ нам потребуется библиотека windows.h, которая есть во всех современных компиляторах. Писать мы будем на Dev C++. Ее можно скачать с официального сайта или прямо у нас. Вот тут —> Скачать Bloodshed Dev C++.
Теперь когда вы установили себе эту прекраснейшую программу перейдем непосредственно к делу. Будем писать (ну может кто-то копировать) код
Сразу скажу, что код программы совсем небольшой, а вот и он:
| #include<iostream> #include<windows.h> using namespace std; int main() { int x; int y; for(int i=0; i<10; ++i) { x=600+rand()%800; y=600+rand()%800; SetCursorPos(x,y); cout<<"\a"; Sleep(600); } } |
Теперь объяснения. Сначала подключаем необходимые библиотеки, а именно iostream и windows.h. После чего создаем две переменные, которые будут отвечать за положение курсора на экране (то есть его координаты). Ну а потом самое интересное
Пускаем цикл до 10 (но если вы хотите реально напугать юзера, то можно и бесконечный) и каждую итерацию присваиваем переменным координат рандомные значение от 600 до 800 (примерно посередине экрана) и теперь внимание, используем функцию SetCursorPos, для смены позиции курсора на экране.
Регистр букв (большие и маленькие) писать точно такой как тут. Иначе функция не будет работать.
Дальше еще немного пугаем юзера и делаем команду
| cout<<"\a"; |
которая будет заставлять процессор (точнее материнскую плату) пикать
Ну и в конце ставим небольшую паузу на полсекунды, чтобы пользователь (жертва) смог заметить куда делся курсор. И так цикл повторяет 10 раз).
Вот, на сегодня все, думаю вам понравится)
C++. Математические операции. Считывание данных.
Опубликовано 01.12.2012 автором admin
Здравствуйте! Скопилось много не рассказанной информации, но все же ее недостаточно для отдельного урока. Поэтому решил выделить ее просто в отдельный пост.
Предыдущие уроки вы можете найти на этой странице.
1) Сокращение выражений:
Часто в программе переменную нужно изменить используя ее в качестве параметра. Пример:
| for (int i = 1; i <= n; i = i + 1) cout << a[i] << " "; cout << "\n"; |
Здесь мы присваиваем значение i + 1 для i, т.е. увеличиваем ее на 1.
Эту и подобные операции можно сократить таким образом:
a += b что равносильно a = a + b;
Также можно сократить любое выражение, включая бинарные.
Пример:
| counter >>= (((a + b) / 15) % 13) & 1; |
Сначала будет выполнятся операции справа от «>>=», лишь затем затем значение counter будет изменено.
Вот все эти сокращения:
| a += b -> a = a + b; a -= b -> a = a - b; a *= b -> a = a * b; a /= b -> a = a / b; a %= b -> a = a % b; a >>= b -> a = a >> b; a <<= b -> a = a << b; a &= b -> a = a & b; a ^= b -> a = a ^ b; a |= b -> a = a | b; |
Их использование не обязательно, но код с такими сокращениями более удобен.
Дата добавления: 2015-09-10; просмотров: 51 | Поможем написать вашу работу | Нарушение авторских прав |