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

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

  • автор:

Зачем нужен префикс m_ или суффикс _ в именах членов класса, если есть квалификация?

Как правило в структурах Си нет методов и следовательно никаких this.
В структурах(классах) C++ могут быть методы, параметры которых скрывают одноименные члены класса. Типичный пример — метод Set():

class X < int n; public: void Setn( int n); >; void X::Setn( int n)

У меня возник вопрос — зачем загромождать имена в классе префиксами «m_» или суффиксами «_»?
Попытка предотвратить забывчивость квалификации X.
Незнание?
В чем смысл?

  • 1 frag / 2 deaths
  • Участник

#1
11:43, 22 янв 2015

graveman
> X::n
так разве можно к нестатическим полям?

по теме — чтобы было понятно сразу, что если у нас некое n, то это поле, и чтоб не надо было листать вверх до заголовка
в коротких функциях, на 1-2строчки — не страшно
в длинных не стоит делать одинаковое имя

#2
11:50, 22 янв 2015

TarasB
> graveman
> > X::n
> так разве можно к нестатическим полям?
Стандарт не читал, но Липман в полном руководстве(ну и Страуструп в справочнике) пишет, что можно.

#3
11:52, 22 янв 2015

_name для приватных
local_name для локальных переменных в методах
a_name для аргументов в функциях

  • Kartonagnick
  • Постоялец

#4
11:56, 22 янв 2015

graveman
> Попытка предотвратить забывчивость квалификации X.

Попытка предотвратить путаницу со статическими полями.

void X::Setn( int n) < X::n = n; // >

graveman
> но Липман

Лимпан не пишет, что каноничное (граммар-наци-корректное) обращение к мемберам внутри класса через this?

void X::Setn( int n) < this->n = n; // >
  • Imaginary unit
  • Постоялец

#5
12:06, 22 янв 2015

Я юзаю:
m_var — для членов класса
var — для локальных переменных
_var — для аргументов функций

В основном, для читабельности.

#6
12:09, 22 янв 2015

Kartonagnick
> Лимпан не пишет, что каноничное (граммар-наци-корректное) обращение к мемберам
> внутри класса через this?
Пишет в 13.9.1.

#7
12:13, 22 янв 2015

graveman
> У меня возник вопрос — зачем загромождать имена в классе префиксами «m_» или
> суффиксами «_»?
Это традиция как продолжение венгерской нотации. С приходом современных IDA, подсвечивающих тип и принадлежность элемента, подобные префиксы стали не сильно актуальны.

В C# префиксы изначально мало кто использует. C++ некоторые используют по привычке.

Все на ваше усмотрение.

#8
12:17, 22 янв 2015

graveman
> У меня возник вопрос — зачем загромождать имена в классе префиксами «m_» или суффиксами «_»?
Не нужно. Уродует код.

  • Kartonagnick
  • Постоялец

#9
12:19, 22 янв 2015

graveman
> Пишет в 13.9.1.

Для шаблонов критично использовать именно каноничную форму

this->member;

Для не-шаблонов префиксы тупо удобнее.

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

X::static_data;

Должно быть использовано только и только для обращения к статическим полям,
либо для вызова методов базовых классов.

За обращение к обычным полям можно ссаными тряпками огребсти (не пройти ревью кода).

#10
12:20, 22 янв 2015

Barabus
> Это традиция как продолжение венгерской нотации.
теперь понятно, привычка

#11
12:27, 22 янв 2015

Kartonagnick
> Вот это:
>
> X::static_data;
>
> Должно быть использовано только и только для обращения к статическим полям,
> либо для вызова методов базовых классов.

Так-то да, можно подумать, что используется статический член.

> Для шаблонов критично использовать именно каноничную форму
>
> this->member;
но просто member быстрее
Вывод — префиксы используются для быстродействия и во избежание путаницы со статическими членами.

#12
12:29, 22 янв 2015

SunnyBunny
> Не нужно. Уродует код.
Согласен, если класс небольшой.

m_x, m_y, m_z

выглядит не очень

  • Kartonagnick
  • Постоялец

#13
12:30, 22 янв 2015

graveman
> но просто member быстрее
> Вывод — префиксы используются для быстродействия и во избежание путаницы со
> статическими членами.

Смысли быстрее?
Вы сейчас о чем?

#14
12:41, 22 янв 2015

Kartonagnick
> Смысли быстрее?
> Вы сейчас о чем?

void X::f( int n) < int tmp = this->n;//*((DWORD*)this + offset_n) > void X::f( int n) < int tmp = m_n;// >

Префикс-функция. Алгоритм Кнута-Морриса-Пратта

Префикс-функция от строки \(s\) равна массиву \(\pi\), где \(\pi[i]\) обозначает длину максимального префикса строки \(s[0..i]\), совпадающего с её суффиксом. Тривиальные случаи (префикс равен суффиксу и равен всей строке) не учитываются.

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

На изображении обозначены равные подстроки, длина которых равна значению префикс-функции в данной позиции. Префикс-функция от всей строки “abacaba” равна \(\\). \(\pi[0] = \pi[1] = 0\) так как строки “a” и “ab” являются тривиальными, и поэтому не учитываются.

В определённых случаях префикс и суффикс могут перекрываться:

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

Наивный алгоритм нахождения префикс-функции имеет сложность \(O(N^3)\), что неприемлемо для большинства случаев. Существует гораздо более эффективный алгоритм, работающий за \(O(N)\).

Алгоритм Кнута-Морриса-Пратта

Алгоритм Кнута-Морриса-Пратта (КМП) позволяет находить префикс-функцию от строки за линейное время, и имеет достаточно лаконичную реализацию, по длине не превышающую наивный алгоритм.

Для начала заметим важное свойство: \(\pi[i] \le \pi[i — 1] + 1\). То есть префикс-функция от следующего элемента не более чем на \(1\) превосходит префикс-функцию от текущего. Случай \(\pi[i] = \pi[i — 1] + 1\) легко изобразить:

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

То есть верно следующее утверждение (в 0-индексации):

\[s[i] = s[\pi[i — 1]] \Rightarrow \pi[i] = \pi[i — 1] + 1\]

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

Если же длина \(j\) также не подходит (\(s[i] \ne s[j]\)), просто ещё раз уменьшим её по такой же формуле: \(j = \pi[j — 1]\). Таким образом будем пытаться продолжить префикс длины \(j\), пока \(j\) не станет равно \(0\). В таком случае просто сравним \(s[i]\) с \(s[0]\), и в зависимости от результата присвоим \(\pi[i] = 0\) или \(1\).

Реализация

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
vectorint> prefix_function(const string& s)  vectorint> pi(s.length(), 0); for (int i = 1; i  s.length(); i++)  int j = pi[i - 1]; //текущая длина префикса, который мы хотим продолжить //гарантируется, что s[0..j-1] = s[i-j..i-1]. while (j > 0 && s[i] != s[j])  //пока мы не можем продолжить текущий префикс j = pi[j - 1]; //уменьшаем его длину до следующей возможной > //Теперь j - максимальная длина префикса, который мы можем продолжить, //или 0, если такового не существует. if (s[i] == s[j])  pi[i] = j + 1; > else  //такое может произойти только при j = 0 pi[i] = j; > > return pi; > 

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

Префикс-функция - необычайно мощная структура, с помощью которой решается значительная часть задач про строки. Классической задачей на префикс-функцию является задача на поиск подстроки в строке (алгоритм КМП был изначально разработан именно для решения этой задачи). Разберём её в качестве примера.

Пусть нам нужно найти подстроку \(t\) в строке \(s\). С помощью префикс-функции это делается тривиально: найдём префикс-функцию от строки \(t + \# + s\) (решётка обозначает символ, гарантированно не встречающийся ни в одной из строк). Если эта префикс-функция содержит значения равные длине \(t\), значит \(t\) входит в \(s\). А именно, пусть \(\pi[i] = \vert t \vert\). Значит \(s[i - \vert t \vert - 1]\) - последний символ вхождения \(t\) в \(s\).

Реализация на C++:

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
#include  using namespace std; vectorint> prefix_function(const string& s)  vectorint> pi(s.length(), 0); for (int i = 1; i  s.length(); i++)  int j = pi[i - 1]; while (j > 0 && s[i] != s[j])  j = pi[j - 1]; > if (s[i] == s[j])  pi[i] = j + 1; > else  pi[i] = j; > > return pi; > int main()  string s, t; cin >> s >> t; vectorint> pi = prefix_function(t + '#' + s); int t_len = t.length(); for (int i = 0; i  s.length(); i++)  if (pi[t_len + 1 + i] == t_len)  cout  <"s["  <i - t_len + 1  <".."  <i  <"] = t"  <endl; > > > 

brestprog

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

Здесь и далее считаем, что символы в строках нумеруются с [math]0[/math] .

Определим префикс-функцию от строки [math]s[/math] в позиции [math]i[/math] следующим образом: [math]\pi(s, i) = \max\limits_ \[/math] . Если мы не нашли такого [math]k[/math] , то [math]\pi(s, i)=0[/math] .

Наивный алгоритм

Наивный алгоритм вычисляет префикс-функцию непосредственно по определению, сравнивая префиксы и суффиксы строк. Обозначим длину строки за [math]n[/math] . Будем считать, что префикс-функция хранится в массиве [math] p [/math] .

Псевдокод

int[] prefixFunction(string s): int[] p = int[s.length] fill(p, 0) for i = 0 to s.length - 1 for k = 0 to i - 1 if s[0..k] == s[i - k..i] p[i] = k return p

Пример

Рассмотрим строку [math]abcabcd[/math] , для которой значение префикс-функции равно [math][0,0,0,1,2,3,0][/math] .

Шаг Строка Значение функции
[math]1[/math] a 0
[math]2[/math] ab 0
[math]3[/math] abc 0
[math]4[/math] abca 1
[math]5[/math] abcab 2
[math]6[/math] abcabc 3
[math]7[/math] abcabcd 0

Время работы

Всего [math]O(n^2)[/math] итераций цикла, на каждой из который происходит сравнение строк за [math]O(n)[/math] , что дает в итоге [math]O(n^3)[/math] .

Эффективный алгоритм

Вносятся несколько важных замечаний:

  • Заметим, что [math]p[i + 1] \leqslant p[i] + 1[/math] . Чтобы показать это, рассмотрим суффикс,оканчивающийся на позиции [math]i + 1[/math] и имеющий длину [math]p[i + 1][/math] , удалив из него последний символ, мы получим суффикс, оканчивающийся на позиции [math]i[/math] и имеющий длину [math]p[i + 1] - 1[/math] , следовательно неравенство [math]p[i + 1] \gt p[i] + 1[/math] неверно.
  • Избавимся от явных сравнений строк. Пусть мы вычислили [math]p[i][/math] , тогда, если [math]s[i + 1] = s[p[i]][/math] , то [math]p[i + 1] = p[i] + 1[/math] . Если окажется, что [math]s[i + 1] \ne s[p[i]][/math] , то нужно попытаться попробовать подстроку меньшей длины. Хотелось бы сразу перейти к такому бордеру наибольшей длины, для этого подберем такое [math]k[/math] , что [math]k = p[i] - 1[/math] . Делаем это следующим образом. За исходное [math]k[/math] необходимо взять [math]p[i - 1][/math] , что следует из первого пункта. В случае, когда символы [math]s[k][/math] и [math]s[i][/math] не совпадают, [math]p[k - 1][/math] — следующее потенциальное наибольшее значение [math]k[/math] , что видно из рисунка. Последнее утверждение верно, пока [math]k\gt 0[/math] , что позволит всегда найти его следующее значение. Если [math]k=0[/math] , то [math]p[i]=1[/math] при [math]s[i] = s[1][/math] , иначе [math]p[i]=0[/math] .

Mprfx.jpg

Псевдокод

int[] prefixFunction(string s): p[0] = 0 for i = 1 to s.length - 1 k = p[i - 1] while k > 0 and s[i] != s[k] k = p[k - 1] if s[i] == s[k] k++ p[i] = k return p

Время работы

Время работы алгоритма составит [math]O(n)[/math] . Для доказательства этого нужно заметить, что итоговое количество итераций цикла [math]\mathrm[/math] определяет асимптотику алгоритма. Теперь стоит отметить, что [math]k[/math] увеличивается на каждом шаге не более чем на единицу, значит максимально возможное значение [math]k = n - 1[/math] . Поскольку внутри цикла [math]\mathrm[/math] значение [math]k[/math] лишь уменьшается, получается, что [math]k[/math] не может суммарно уменьшиться больше, чем [math]n-1[/math] раз. Значит цикл [math]\mathrm[/math] в итоге выполнится не более [math]n[/math] раз, что дает итоговую оценку времени алгоритма [math]O(n)[/math] .

Построение префикс-функции по Z-функции

Постановка задачи

Дан массив с корректной Z-функцией для строки [math]s[/math] , получить за [math]O(n)[/math] массив с префикс-функцией для строки [math]s[/math] .

Описание алгоритма

Пусть Z-функция хранится в массиве [math]z[0 \ldots n-1][/math] . Префикс-функцию будем записывать в массив [math]p[0 \ldots n-1][/math] . Заметим, что если [math]z[i] \gt 0, [/math] то для всех элементов с индексом [math]i + j[/math] , где [math]0 \leqslant j \lt z[i] [/math] , значение [math]p[i + j] [/math] будет не меньше, чем длина подстроки с [math] i [/math] по [math] i + j[/math] , что равно [math]j + 1[/math] (как изображено на рисунке).

Также заметим, что если мы уже установили в какую-то позицию значение [math] j [/math] с позиции [math] i [/math] , а потом пытаемся установить значение [math] j' [/math] c позиции [math] i' [/math] , причём [math] i \lt i' [/math] и [math] i + j = i' + j' [/math] , то изменение с позиции [math] i' [/math] только уменьшит значение [math] p[i + j][/math] . Действительно, значение после первого присвоения [math]p[i + j] = j \gt j' = p[i' + j'][/math] . В итоге получаем алгоритм: идем слева направо по массиву [math]z[/math] и, находясь на позиции [math]i[/math] , пытаемся записать в [math]p[/math] от позиции [math]i + z[i] - 1 [/math] до [math]i[/math] значение [math] j + 1,[/math] где [math]j[/math] пробегает все значения [math] 0 \dots z[i] - 1[/math] , пока не наткнемся на уже инициализированный элемент. Слева от него все значения тоже нет смысла обновлять, поэтому прерываем эту итерацию.

Убедимся, что алгоритм работает за линейное время (см. псевдокод). Каждый элемент устанавливается ровно один раз. Дальше на нем может случиться только [math]\mathrm[/math] . Поэтому в итоге внутренний цикл суммарно отработает за количество установленных значений и количество [math]\mathrm[/math] . Количество установленных значений — [math] n[/math] . А число [math]\mathrm[/math] тоже будет не больше [math]n[/math] , так как каждый [math]\mathrm[/math] переводит внешний цикл на следующую итерацию, откуда получаем итоговую асимптотику [math]O(n)[/math] .

ZP4.jpg

Псевдокод

int[] buildPrefixFunctionFromZFunction(int[] z): int[] p = int[z.length] fill(p, 0) for i = 1 to z.length - 1 for j = z[i] - 1 downto 0 if p[i + j] > 0 break else p[i + j] = j + 1 return p

Построение строки по префикс-функции

Постановка задачи

Восстановить строку по префикс-функции за [math]O(n)[/math] , считая алфавит неограниченным.

Описание алгоритма

Пусть в массиве [math]p[/math] хранятся значения префикс-функции, в [math]s[/math] будет записан ответ. Пойдем по массиву [math]p[/math] слева направо.

Пусть мы хотим узнать значение [math]s[i][/math] . Для этого посмотрим на значение [math]p[i][/math] : если [math]p[i] =0[/math] , тогда в [math]s[i][/math] запишем новый символ, иначе [math]s[i] = s[p[i] - 1][/math] . Обратим внимание, что [math]s[p[i] - 1][/math] нам уже известно, так как [math]p[i] - 1 \lt i[/math] .

Реализация

string buildFromPrefix(int[] p): s = "" for i = 0 to p.length - 1 if p[i] == 0 s += new character else s += s[p[i] - 1] return s

Доказательство корректности алгоритма

Докажем, что если нам дали корректную префикс-функцию, то наш алгоритм построит строку с такой же префикс-функцией. Также заметим, что строк с такой префикс-функцией может быть много, и алгоритм строит только одну из них.

Пусть [math]p[/math] — данная префикс-функция, строку [math]s[/math] построил наш алгоритм, [math] q [/math] — массив значений префикс-функции для [math]s[/math] .

Докажем корректность индукцией по длине массива префикс-функции полученной строки. Для начала заметим, что на предыдущие значения массива [math] q [/math] прибавление нового символа не влияет, так как при подсчёте префикс-функции на [math] i [/math] -ой позиции рассматриваются символы на позициях не больше [math] i [/math] . Поэтому достаточно показать, что очередное значение префикс-функции будет вычислено правильно.

  • База очевидна для строки длины [math]1[/math] .
  • Переход: пусть до [math]n[/math] -ой позиции мы построили строку, что [math]p[0 \ldots n - 1] = q[0 \ldots n - 1][/math] . Возможны два случая:
    • [math]p[n] = 0[/math] . Тогда мы добавляем новый символ, поэтому [math]q[n][/math] тоже будет равно [math]0[/math] .
    • [math]p[n] \gt 0[/math] . Бордер строки [math] s[0 \ldots n - 1] [/math] имеет длину [math] p[n-1] = q[n-1] [/math] . Поэтому если дописать к строке [math] s [/math] символ [math] s[q[n] - 1] [/math] , то бордер нашей новой строки [math] s[0 \ldots n] [/math] станет равен [math] p[n] [/math] , как можно увидеть на рисунке.

    Критерий корректности значений префикс-функции

    Задача:
    Дан массив значений префикс-функции некоторой строки [math]s[/math] , необходимо проверить, корректен ли он за [math]O(|s|)[/math] . Так же узнать размер минимального алфавита, при котором он корректен.

    Решение

    Если выполняется неравенство [math]0 \leqslant p[i + 1] \leqslant p[i] + 1[/math] , то мы можем построить строку из алгоритма выше, значит префикс-функция корректна.

    Найдем минимальный алфавит, при котором префикс-функция корректна. Если значение префикс-функции в текущей ячейке больше нуля, буква известна и алфавит не нуждается в добавлении новой буквы. Иначе, необходимо исключить все ранее известные буквы, возвращаясь и проверяя для меньших префиксов. Если все уже известные буквы использованы, понятно что, необходимо добавить новую букву.

    Доказательство корректности

    Докажем, что найденнный выше алфавит минимален от противного. Допустим, существует строка, использующая алфавит меньшей мощности. Рассмотрим первое вхождение буквы, которая есть в нашем алфавите, а в их отсутствует. Понятно, что для этого символа префикс-функция равна 0, т.к. мы добавили новую букву. Пройдемся циклом [math]\mathrm[/math] по подпрефиксам. Т.к. в меньшем решении буква не новая, то она увеличит подпрефикс и префикс-функция в новой строке будет отличаться от нуля в этом символе, а должна равняться нулю. Противоречие, следовательно не существует алфаивта меньшей мощности, чем найденный алгоритмом выше.

    Псевдокод

    bool is_correct(int[] p): for i = 0 to p.length - 1 if i > 0 && p[i] > p[i - 1] + 1 || p[i] < 0 return false return true 
    int minimal_alphabet(int[] p): c = 1 s[0] = 0 for i = 1 to p.length - 1 if p[i] == 0 fill(used, false) k = p[i - 1] while k > 0 used[s[k]] = true k = p[k - 1] s[i] = -1 for j = 1 to c if !used[j] s[i] = j; break if s[i] == -1 s[i] = c++ else s[i] = s[p[i] - 1] return c

    См. также

    • Z-функция
    • Алгоритм Кнута-Морриса-Пратта

    Источники информации

    • Википедия — Префикс-функция
    • MAXimal :: algo :: Префикс-функция
    • Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296 ISBN 978-5-8459-0857-5
    • Алгоритмы и структуры данных
    • Поиск подстроки в строке
    • Точный поиск

    Поиск. КМП-алгоритм

    Недавно на досуге решил написать алгоритм КМП (КнутаМорриса — Пратта) для Scala.

    Изначально, мне нужно было решить простенькую задачку – найти последовательность байт в потоке байтов. Сделал на Java. Потом, решил сделать тоже самое на Scala. Занятно, но в стандартной библиотеке коллекций Scala используется именно КМП поиск.

    Вот мой вариант.

    object KPM < def search(source: Seq[Any], m:Seq[Any]): Int = < // вычисляем значение префикс-функции val p = prefix(m) // длина строки которую ищем (вообще не обязательно строки) val length = m.size // кол-во совпадений var k = 0 // позиция от начала var i = 0 val it = source.iterator // перебираем все элементы while (it.hasNext && k < length) < // тек. элемент val current = it.next // pos - позиция тек. элемента в списке while (k >0 && current != m(k)) < k = p(k - 1) >if (current == m(k)) < // еще одно совпадение k +=1 >// следующая буква i+=1 > // всё совпало if (k == length) < i - length >else < -1 >> // префикс-функция def prefix(s: Seq[Any]):Array[Int] = < val p = new Array[Int](s.size); p(0)=0 for (i < - 1 to s.size-1) < // длина предыдущего префикса var length = p(i - 1) while (length >0 && s(i) != s(length)) < length = p(length - 1) >if (s(length) == s(i)) length += 1 p(i)=length; > return p; > def main(arr : Array[String]) = < val s = "abacaba" val m = "aca" val list = s.toList println(search(s, m)) println(s.indexOf(m)) >>

    Первое (и возможно самое сложно) что нужно сделать — понять что такое префикс-функция.

    Но сначала нужно разобрать что значит вообще префикс и суффикс?
    Если грубо префикс – это подстрока, которая начинается с первого символа. Для строки “happy“, строки ha, happ, h будут являться префиксами.

    Суффикс — он как префикс, только с конца. Например, для строки “happy“, строки “appy“, “y” будут суффиксами.

    Префикс и суффиксы, которые совпадают со всей строкой целиком нас не интересуют.

    Теперь введем понятие префикс-функции. Префикс-функции от строки — длина наибольшего префикса, который не совпадает с этой строкой и одновременно является её суффиксом. Если более простым языком, длина самого большого префикса, который также является и суффиксом (естественно, не совпадает со всей строкой). А если еще проще, длина самых больших одинаковых кусков спереди и сзади строки.

    pi("abacaba") = 3 pi("aba") = 1 pi("ab") = 0

    На самом деле, используют префикс-функцию от двух аргументов – строки и числа. Строка – это исследуемая строка, а число – указывает длину подстроки для которой нужно считать префикс функцию.

    Например для abacaba, Pi(“abacaba”,i)
    P(“abacaba”, 1) = “a”:0
    P(“abacaba”, 2) = “ab”:0
    P(“abacaba”, 3) = “aba”:1
    P(“abacaba”, 4) = “abac”:0
    P(“abacaba”, 5) = “abaca”:1
    P(“abacaba”, 6) = “abacab”:2
    P(“abacaba”, 7) = “abacaba”:3

    получаем P(“abacaba”) =0010123

    Ну а потом читаем википедию ��

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

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