Что такое префикс в программировании
Перейти к содержимому

Что такое префикс в программировании

  • автор:

Префиксные операторы увеличения и уменьшения ++ и —

Оператор добавочного префикса (++) добавляет один к операнду. Это добавочное значение является результатом выражения. Операнд должен быть l-значением не типа const . Результат — L-значение того же типа, как у операнда.

Оператор декремента префикса () аналогичен оператору добавочного префикса, за исключением того, что операнд уменьшается по одному, и результатом является это уменьшение значения.

Visual Studio 2017 версии 15.3 и более поздних версий (доступных в /std:c++17 режиме и более поздних версиях): операнд оператора добавочного или декремента может не быть типа bool .

Операторы префиксных и постфиксных инкремента и декремента влияют на свои операнды. Они различаются между собой порядком выполнения инкремента или декремента при вычислении выражения (Дополнительные сведения см. в разделе Операторы приращения и декремента.) В форме префикса приращение или уменьшение происходит до использования значения в оценке выражений, поэтому значение выражения отличается от значения операнда. В постфиксной форме инкремент или декремент выполняется после использования значения при вычислении выражения, поэтому значение выражения совпадает со значением операнда. Например, в следующей программе выполняется вывод на печать » ++i = 6 «.

// expre_Increment_and_Decrement_Operators.cpp // compile with: /EHsc #include using namespace std; int main()

Операнд целочисленного типа или типа с плавающей запятой инкрементируется или декрементируется на целое значение 1. Тип результата совпадает с типом операнда. Операнд типа указателя инкрементируется или декрементируется на значение размера объекта, к которому он относится. Инкрементированный указатель указывает на следующий объект, а декрементированный — на предыдущий.

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

// expre_Increment_and_Decrement_Operators2.cpp #define max(a,b) ((a)

Макрос разворачивается до следующего выражения:

k = ((++i)<(j))?(j):(++i); 

Если значение i больше или равно j или меньше j на 1, оно будет инкрементировано дважды.

Встраиваемые функции C++ предпочтительнее макросов во многих случаях, поскольку исключают побочные эффекты, подобные описанным здесь, и позволяют языку выполнять более полную проверку типов.

О пользе префиксов

Я хочу рассказать о не совсем очевидной пользе префиксов в названиях имён и типов. Я считаю что у любых разработок у которых наличествует внешнее апи, должны быть префиксы, причём не с потолка взятые а тщательно выбранные.
Всё дело в удобстве поиска информации. Я уже почти год знаком с box2d, чуть больше с SDL и около двух месяцев как начал писать под ios (cocoa). И при работе с этими библиотеками я ощутил необыкновенную легкость и удобность. И совсем недавно, когда опять плотно занялся actionScript понял, чем те библиотеки отличаются от стандартного рантайма Adobe: префиксами. И дело не в коде, не в наличии пакетов или неймспейсов. Дело в гуглении. Это же просто шикарно, набрать в гугле SDL_MOUSEBUTTONDOWN, или NSArray или b2Shape и сразу получить то, что вы ищите. Это огромный плюс, возможность мгновенно находить то что вам нужно, очень важная часть хорошего апи. Чтобы найти документацию или сторонние обсуждения к Array от Adobe надо приписывать всякие штуки, типа as3 или Adobe, некоторые статьи теряются и не находятся таким образом. По запросу «array sort» гуглится и msdn и java и flash и php.

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

Данный текст опубликован под лицензией CC-BY.

  • префиксы
  • префиксная нотация

Префикс-функция

Определение. Префикс-функцией от строки $s$ называется массив $p$, где $p_i$ равно длине самого большого префикса строки $s_0 s_1 s_2 \ldots s_i$, который также является и суффиксом $i$-того префика (не считая весь $i$-й префикс).

Например, самый большой префикс, который равен суффиксу для строки «aataataa» — это «aataa»; префикс-функция для этой строки равна $[0, 1, 0, 1, 2, 3, 4, 5]$.

 Этот алгоритм пока что работает за $O(n^3)$, но позже мы его ускорим.

#Как это поможет решить исходную задачу?

Давайте пока поверим, что мы умеем считать префикс-функцию за линейное от размера строки, и научимся с помощью нее искать подстроку в строке.

Соединим подстроки $s$ и $t$ каким-нибудь символом, который не встречается ни там, ни там — обозначим пусть этот символ # . Посмотрим на префикс-функцию получившейся строки s#t .

 Видно, что все места, где значения равны 6 (длине $s$) — это концы вхождений $s$ в текст $t$.

Такой алгоритм (посчитать префикс-функцию от s#t и посмотреть, в каких позициях она равна $|s|$) называется алгоритмом Кнута-Морриса-Пратта.

#Как её быстро считать

Рассмотрим ещё несколько примеров префикс-функций и попытаемся найти закономерности:

Можно заметить следующую особенность: $p_$ максимум на единицу превосходит $p_i$.

Доказательство. Если есть префикс, равный суффиксу строки $s_$, длины $p_$, то, отбросив последний символ, можно получить правильный суффикс для строки $s_$, длина которого будет ровно на единицу меньше.

Попытаемся решить задачу с помощью динамики: найдём формулу для $p_i$ через предыдущие значения.

Заметим, что $p_ = p_i + 1$ в том и только том случае, когда $s_ =s_$. В этом случае мы можем просто обновить $p_$ и пойти дальше.

Например, в строке $\underbracet\overbrace$ выделен максимальный префикс, равный суффиксу: $p_ = 5$. Если следующий символ равен будет равен $t$, то $p_ = p_ + 1 = 6$.

Но что происходит, когда $s_\neq s_$? Пусть следующий символ в этом же примере равен не $t$, а $b$.

  • $\implies$ Длина префикса, равного суффиксу новой строки, будет точно меньше 5.
  • $\implies$ Помимо того, что искомый новый супрефикс является суффиксом «aabaab», он ещё является префиксом подстроки «aabaa».
  • $\implies$ Значит, следующий кандидат на проверку — это значение префикс-функции от «aabaa», то есть $p_4 = 2$, которое мы уже посчитали.
  • $\implies$ Если $s_2 = s_$ (т. е. новый символ совпадает с идущим после префикса-кандидата), то $p_ = p_2 + 1 = 2 + 1 = 3$.

В данном случае это действительно так (нужный префикс — «aab»). Но что делать, если, в общем случае, $p_ \neq p_$? Тогда мы проводим такое же рассуждение и получаем нового кандидата, меньшей длины — $p_>$. Если и этот не подошел — аналогично проверяем меньшего, пока этот индекс не станет нулевым.

   Асимптотика. В худшем случае этот while может работать $O(n)$ раз за одну итерацию, но в среднем каждый while работает за $O(1)$.

Префикс-функция каждый шаг возрастает максимум на единицу и после каждой итерации while уменьшается хотя бы на единицу. Значит, суммарно операций будет не более $O(n)$.

Префикс-функция

Префикс-функция строки s — массив длин максимальных бордеров всех префиксов s. Бордер — собственный префикс, одновременно являющийся собственным суффиксом.

vector prefixFunction(const string &s) < vectorp(s.size()); for (int i = 1; i < s.size(); i++) < int border = p[i - 1]; while (border >0 && s[i] != s[border]) border = p[border - 1]; p[i] = border + (s[i] == s[border]); > return p; >
  • Поиск подстроки pattern в тексте text за O(N) (алгоритм Кнута-Морриса-Пратта). Составляется строка pattern#text, вычисляется её префикс-функция. Вхождения завершаются в позициях, для которых p[i] == pattern.size().
  • Определение минимального периода period строки s за O(N). period = s.size() - p.back().
  • Определение числа различных подстрок строки s за O(N^2). Пусть известен ответ prevRes для строки prevSuffix = s.substr(i + 1), за O(N) вычислим ответ res для строки suffix = s.substr(i). Новые подстроки — те, которые начинаются в начале строки и не встречаются далее. Вычисляем префикс-функцию для suffix, пусть maxP = *max_element(p.begin(), p.end()). В prevSuffix уже встречались все префиксы длиной ≤ maxP, поэтому res = prevRes + (suffix.size() - maxP).

Ссылки

  • e-maxx.ru — Префикс-функция. Алгоритм Кнута-Морриса-Пратта
  • neerc.ifmo.ru/wiki — Префикс-функция
  • neerc.ifmo.ru/wiki — Алгоритм Кнута-Морриса-Пратта
  • Brestprog — Префикс-функция. Алгоритм Кнута-Морриса-Пратта
  • Algorithmica — Префикс- и Z-функция
  • Brilliant.org — Knuth-Morris-Pratt Algorithm
  • github.com/indy256/codelibrary/blob/master/cpp/strings/kmp.cpp
  • github.com/ADJA/algos/blob/master/Strings/PrefixFunction.cpp
  • informatics.mccme.ru — Курс «Алгоритмы на строках» — часть 1
  • Задачи: Префикс-функция

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *