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

Префикс (информатика)

В информатике подстрока — это непустая связная часть строки.

Формальное определение

Пусть $L=c_0\dots c_<n-1>» width=»» height=»» /> — строка длины <i>n</i> . <br />Любая строка <img decoding=$ , где $0\le i\le j\le n-1$ , является подстрокой L длины j − i + 1 .
Если i = 0 , то S называется префиксом L длины j + 1 .
Если j = n − 1 , то S — суффикс L длины j − i + 1 .

Пример

С точки зрения информатики строки «кипед», «Вики», «дия» являются подстроками строки «Википедия»; при этом «Вики» — префиксом, а «дия» — суффиксом.

Получение подстроки

Если line — исходная строка, begin — позиция первого символа подстроки, end — позиция последнего символа подстроки, то подстрока subline вычисляется следующим образом:

В языке C

char * subline = (char *)malloc(end — begin + 2);
if (subline == NULL)
<
fprintf(stderr, «ERROR: malloc failed!»);
exit(1);
>
subline[end — begin + 1] = ‘\0’;

В языке python подстрока является слайсом (срезом) (англ. slice ).

В языке

В языке Pascal

SubStr := Copy(SourceStr, StartCharIndex, SubStrLength);

Операции с подстрокой

Помимо простой задачи выделения подстроки из строки по двум индексам существует и более сложная задача поиска индексов, указывающих на заданную подстроку в строке (поиск вхождения подстроки в строку).

См. также

Wikimedia Foundation . 2010 .

Полезное

Смотреть что такое «Префикс (информатика)» в других словарях:

Суффиксное дерево — Суффиксное дерево бор, содержащий все суффиксы некоторой строки (и только их). Позволяет выяснять, входит ли строка w в исходную строку t, за время O(|w|), где |w| длина строки w. Содержание 1 Основные определения и описание структуры … Википедия

Дерево суффиксов — Суффиксное дерево способ организации данных (строк), позволяющий выяснять, входит ли строка w в строку t, за время O(|w|), где |w| длина строки w. Содержание 1 Основные определения и описание структуры 2 Свойства суффиксных д … Википедия

Идентификатор цифрового объекта — (также используется словосочетание Цифровой идентификатор объекта, ЦИО, digital object identif … Википедия

Пи-исчисление — исчисление в теоретической информатике исчисление процессов, изначально разработанное Робином Милнером, Иоахимом Парровом и Дэвидом Уолкером как продолжение работы над исчислением общающихся систем. Целью исчисления является возможность… … Википедия

Франция — (France) Французская Республика, физико географическая характеристика Франции, история Французской республики Символика Франции, государственно политическое устройство Франции, вооружённые силы и полиция Франции, деятельность Франции в НАТО,… … Энциклопедия инвестора

Зализняк, Андрей Анатольевич — Андрей Анатольевич Зализняк А. А. Зализняк во время лекции о берестяных грамотах из раскопок 2008 года Дата рождения … Википедия

Префиксное дерево — Префиксное дерево абстрактный тип данных (АТД), структура данных, позволяющая хранить ассоциативный массив, ключами которого являются строки. В отличие от б … Википедия

Префиксный код — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. Префиксный код в теории кодирования код со словом переменной длины, имеющий такое св … Википедия

Позиционная система — счисления система счисления, в которой один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен. Изобретение позиционной нумерации, основанной на поместном значении цифр … Википедия

String algorithms: What is the prefix function and how to compute it

The prefix function is used by many string algorithms, including the Knuth-Morris-Pratt algorithm for string matching. This article derives, implements and analyses an algorithm which computes the prefix function of a given string in linear time.

Notations, terminology

I will use the following notations and terminology throughout this article:

Unless otherwise specified, capital letters refer to strings and their lowercase version to their length (e.g. S is a string of length s).
An index of S is an integer between 1 and s inclusive.
TU denotes the string made by concatenating T and U, where T and U may be strings or characters.
For all indices i, j of T, T[i] denotes the i-th character of T and T[i .. j] denotes the string T[i] … T[j].

Borders and the prefix function

We consider a string S. We can then define borders as follows:

Definition:

A border of S is a string B which is a proper prefix and a proper suffix of S.

For example, the empty string ε is a border of any non-empty string, but ε has no borders (because its only substring is itself, which is not a proper prefix or suffix). The longest border of the string baobaba is ba .

Definition:

The prefix function of S is the function �� that maps indices i of S to the length of the longest border of S[1 .. i].

For example if we consider the string baobaba then ��(1) = ��(2) = ��(3) = 0, ��(4) = 1, ��(5) = 2, ��(6) = 1 and ��(7) = 2.

Our goal is to write an algorithm which takes a string and gives its prefix function.

Paving our way

The first interesting property of borders tells us that every border of S is the longest border of a substring of S. More precisely:

Property 1:

The n-th longest border of S is the longest border of the (n-1)-th longest border of S.

The proof is something along those lines:

Proof outline:

We can start by proving that if A and B are borders of S, then a < b implies that A is a border of B. In particular, the n-th longest border of S is a border of the (n-1)-th. We now need to prove that it is the longest. Suppose that it is not: the (n-1)-th longest border of S has a border B which is strictly longer than the n-th longest border of S. Since B is a border of a border of S, it must be a border of S as well. It is strictly shorter than the (n-1)-th longest and strictly longer than the n-th longest: this is impossible.

We will use this property to derive a recurrence relation to find all values of ��.

The base case is simple: the longest border of a string containing one single character is ε. Therefore, ��(1) = 0.

Suppose that S has length s ≥ 2. B is a non-empty border of S if and only if the following conditions are all satisfied:

B[b] = S[s];
B[1 .. b — 1] = S[s — b .. s — 1];
B[b] = S[b];
B[1 .. b — 1] = S[1 .. b — 1];
b ≤ s — 1.

We have just rephrased the definition in a way that separates the last symbol of the border from the rest. Statements 1. and 2. are equivalent to saying that B is a suffix of S, statements 3. and 4. are equivalent to saying that B is a prefix of S and statement 5. implies that B is a proper prefix/suffix of S. This enables to find a relation between borders of S and borders of S[1 .. s — 1]:

B is a non-empty border of S if and only if: B[1 .. b — 1] is a border of S[1 .. s — 1] and B[b] = S[b] = S[s].

It means that any border of S is constructed by appending S[s] to a border of S[1 .. s — 1], provided that S[s] = S[b]. Therefore:

Property 2:

S has a non-empty border of length b if and only if: S[1 .. s — 1] has a border of length b — 1 and S[b] = S[s].

Writing a solution

We can thus establish the following informal algorithm:

To find ��(i), iterate over all border lengths b of S[1 .. i — 1] in decreasing order. The first time S[b + 1] = S[i], we set ��(i) = b + 1. If it never happens, ��(i) = 0.

So we start with the longest border of S[1 .. i-1], of length ��(i-1). If S[��(i — 1) + 1] = S[i], we can set ��(i) = ��(i-1) + 1. Otherwise, we need to find the length of the second longest border of S[1 .. i-1]. Property 1 tells us that it is given by ��(��(i — 1)): the second longest border of S is the longest border of the longest border of S. So we need to check if S[1 .. ��(��(i — 1)) + 1] = S[i], in which case we set ��(i) = ��(��(i — 1)) + 1. We repeat until we find the longest border — if we never find it, we set ��(i) = 0.

This gives the following algorithm in pseudocode (array and string indices start at 1):

We start by initialising an array which corresponds to the prefix function (line 4) and set its first value to 0 (it is the base case).

The while loop (line 10) iterates over all border lengths of S in a decreasing order. We make sure that borderLength remains positive (��(0) would not make any sense). If the ( borderLength + 1)-th character of the string is equal to the i-th one then we’ve found our longest border (it has length borderLength + 1).

If the condition line 13 is satisfied then we have found the length of the longest border of S[1 .. i] and set the value of borderLength accordingly. Otherwise, borderLength is zero, which corresponds to the maximum border length of S[1 .. i].

We can therefore define ��(i) and move on.

Analysis

As promised, the algorithm runs in Θ(s) time with respect to the length of the string. This is not obvious, in particular because of the while loop.

The only variable which determines the number of iterations of the while loop is borderLength . It is initialised at 0 and can increase (line 14) or decrease (line 11).

Since borderLength is always nonnegative, it cannot decrease more than it increases. It increases by no more than s — 1 (once per iteration of the for loop), which proves that the while loop runs no more than s — 1 times throughout the execution of the programme.

Since the for loop runs exactly s — 1 times, the total complexity of compute-�� is Θ(s).

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

В компьютерном программировании соглашение об именах — набор правил для выбора последовательности символов, которая будет использоваться для идентификаторов, которые обозначают переменные, типы, функции и другие объекты в исходном коде и документации, — «Википедия»

Придумывать названия сложно!

В этой статье мы сосредоточимся на методе именования (P)A/HC/LC для того, чтобы улучшить читаемость кода. Эти рекомендации можно применить к любому языку программирования, в статье для примеров кода используется JavaScript.

Что значит (P)A/HC/LC?

В этой практике используется следующий шаблон для именования функции:

Что обозначает префикс (P)?

Префикс расширяет смысл функции.

Описывает свойство или состояние текущего контекста (обычно — логическое значение).

Указывает, имеет ли текущий контекст определенное значение или состояние (обычно — логическое значение).

Отражает положительный условный оператор (обычно — логическое значение), связанный с определенным действием.

Действие — это сердце функции

Действие — это глагольная часть имени функции. Это самая важная часть в описании того, что делает функция.

Получает доступ к данным немедленно (сокращение от getter для внутренних данных).

Безусловно присваивает переменной со значением A значение B.

Возвращает переменную к её начальному значению или состоянию.

Выполняет запрос данных, для которого требуется время (например, асинхронный запрос).

Удаляет что-то откуда-то.

Например, если у вас есть коллекция выбранных фильтров на странице поиска, удаление одного из них из коллекции — это removeFilter , а не deleteFilter (именно так вы и скажете на английском языке):

Полностью стирает что-то. После операции сущность перестаёт существовать.

Представьте, что вы редактор контента, и есть пост, от которого вы хотите избавиться. Как только вы нажали на кнопку delete-post, CMS выполнила действие deletePost , а не removePost .

Создает новые данные из существующих. Обычно это применимо к строкам, объектам или функциям.

Обработка действия. Часто используется при именовании обратного вызова.

Контекст

Контекст — это область, с которой работает функция.

Функция — это часто действие с чем-то. Важно указать, какова её рабочая область или, по крайней мере, ожидаемый тип данных.

В итоге

Пять принципов именования переменных

В этом разделе мы предложим некоторые правила именования переменных, которые улучшат читаемость кода.

1. Следуйте S-I-D

Имя должно быть коротким (Short), интуитивно понятным (Intuitive) и описательным (Descriptive).

2. Избегайте сокращений

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

3. Избегайте дублирования контекста

Всегда удаляйте контекст из имени, если это не снижает его читабельность.

4. Отражайте в имени ожидаемый результат

5. Учитывайте единственное/множественное число

Как и префикс, имена переменных могут быть единственного или множественного числа в зависимости от того, имеют ли они одно значение или несколько.

6. Используйте осмысленные и произносимые имена

Стиль программирования, соглашения об именовании

Хорошее имя имеет огромное значение для читабельности программы. Такие имена, как proc1 , proc2 , и proc3 ничего не означают, но даже кажущиеся достойными имена могут быть сомнительными. Например, чтобы назвать функцию, которая принимает два диапазона и вычисляет сумму первых, которая лежит в пределах второй, могут показаться уместными имена, как computeRangeWithinRange . К сожалению, это имя не дает никакой информации о порядке аргументов функции. Иногда это не будет проблемой, потому что интеллектуальная интегрированная среда разработки должна помочь вам определить имена аргументов функции, но это может ввести в заблуждение, когда код будет напечатан, или когда вы пытаетесь быстро прочитать код. Лучше дать имя computeRangeWithinFirstRange , которое по крайней мере, покажет порядок аргументов функции.

Общие соглашения об именовании

Как правило, лучше выбрать набор соглашений об именовании для использования во всем коде. Соглашения об именовании обычно регулируют такие вещи, как использование переменных, классов и функций, будете ли вы включать префикс для указателей, статические или глобальные данные, и как вы указываете то, что является закрытым полем класса.

Есть много общего в именовании классов, функций и объектов. Обычно они разбиты на несколько основных категорий: си-стиль именования, camelCase и CamelCase . Си-стиль именования отделяет слова в имени, используя подчеркивание: this_is_an_identifer . Есть две формы CamelCase : первая начинается со строчной буквы, затем первая буква каждого последующего слова прописная, и вторая, где первая буква каждого слова прописная.

Одним из популярных соглашений является то, что прописные буквы CamelCase используются для имен структур и классов, в то время как camelCase используется для имен функций и переменных (хотя иногда переменные записываются в си-стиле, чтобы сделать визуальное разделение между функциями и переменными более ясным).

Может быть полезно использовать префиксы для определенных типов данных, чтобы напомнить вам, какие они есть: например, если у вас есть указатель pointer , стоящее перед ним p_ скажет вам, что это указатель. Если вы видите соответствие между переменными, одна из которых начинается с p_ , а другая нет, то вы сразу понимаете, что это подозрительно. Также может быть полезно использовать префикс для глобальных или статических переменных, поскольку каждая из них ведет себя не так, как обычные локальные переменные. В случае глобальных переменных, особенно полезно использовать префикс для предотвращения конфликтов имен с локальными переменными (что может привести к путанице).

Наконец, частое соглашение — ставить подчеркивание перед закрытыми полями и методами класса, например: _private_data . Это помогает легче находить объявления методов в теле класса, а также покажет, что вы должны и не должны делать с переменной. Например, общее правило избегать возвращения неконстантных ссылок на поля класса от функций, которые являются более открытыми, чем поле. Например, если _age является закрытым полем, то открытая функция getAge , вероятно, не должна возвращать неконстантную ссылку, поскольку это дает полный доступ к закрытому полю!

Венгерская нотация

Венгерская нотация связана с префиксом переменных с информацией об их типе — например, является ли переменная integer или double. Обычно этого не стоит делать, потому что ваш IDE подскажет вам тип переменной, а такой стиль может привести к странным и сложным именам. Оригинальная идея венгерской нотации, была более общей и полезной: создание абстрактных имен с помощью префиксов, которые описывают использование переменной, а не ее представление. Есть префиксы, которые задают тип переменной, например: s — string , b — bool , g_ — global и т. д. А есть префиксы которые задают смысл этой переменной, например: i — index , n — number и т. д. Это может быть полезно для разделения указателей и целых чисел, а также может быть мощным средством разделения понятий, которые часто используются вместе, но которые не следует путать.

Сокращения

Сокращения опасны — гласные буквы полезны и могут ускорить считывание кода. Использование сокращений может быть полезно, когда имя очень длинное, потому что слишком длинные имена столь же трудно читать, как и слишком короткие. Будьте последовательны, если это возможно, и ограничивайте себя в использовании сокращений.

Общие сокращения включают « itr » для « iterator » или « ptr » для pointer . Даже такие имена, как i , j , k прекрасно подходят для счетчика цикла переменных (в первую очередь потому, что они так часто употребляются). Неудачные сокращения похожи на cmptRngFrmRng , которые, экономя лишь несколько букв, затрудняют чтение. Если вы не хотите набирать длинные имена, поищите авто-завершение в вашем текстовом редакторе. Вам не придется часто вводить полный идентификатор. (На самом деле, вы редко об этом задумываетесь: опечатки невероятно трудно обнаружить.)