Что такое подстрока в строке

Подстрока

Содержание

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

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

Пусть — строка с длиной .
Любая строка , где , является подстрокой с длиной .
Если , то называется префиксом с длиной .
Если , то — суффикс с длиной .

Пример

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

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

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

В языке C

В языке Python

subline = line[begin:end + 1]

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

В языке Perl

В языке PHP

В языке Pascal

В языке Ruby

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

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

См. также

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

Полезное

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

подстрока — подстрок а, и, мн. ч. оки, ок (инф.) … Русский орфографический словарь

подстрока строки символов — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN substring of a string of symbols … Справочник технического переводчика

подстарок — подстрока … Краткий словарь анаграмм

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

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

Префикс (информатика) — Содержание 1 Формальное определение 2 Пример 3 Получение подстроки 3.1 В языке C … Википедия

Алгоритм Рабина — Карпа — это алгоритм поиска строки, который ищет шаблон, то есть подстроку, в тексте используя хеширование. Он был разработан в 1987 году Майклом Рабином и Ричардом Карпом. Алгоритм редко используется для поиска одиночного шаблона, но имеет значительную… … Википедия

LZ77 — и LZ78 алгоритмы сжатия без потерь, опубликованные в статьях Абрахама Лемпеля (англ.) и Якоба Зива (англ.) в 1977 и 1978 годах. Эти алгоритмы наиболее известные варианты в семействе LZ*, которое включает в себя также LZW, LZSS,… … Википедия

Алгоритм Бойера — Мура — Хорспула — Алгоритм Бойера Мура Хорспула поиска строки упрощённый вариант алгоритма Бойера Мура. АБМХ работает лучше алгоритма Бойера Мура на случайных текстах. К тому же, требующая многих предварительных вычислений эвристика… … Википедия

Источник

Поиск подстроки в строке

Задача поиска подстроки одна из достаточно распространённых в информатике. Строкой называют последовательность символов (в произвольном порядке) взятых из заданного алфавита. Так например, алфавитом могут быть цифры <0, 1>из которых можно составлять неограниченную по длине цепочку символов, например, 0110100110 или 0. Понятие алфавита и другие раскрываются в теории формальных языков.

В рамках этой статьи рассмотрены задачи нахождения одной строки в другой. Результатом поиска могут быть как простой ответ «да / нет» на вопрос «содержит ли данная строка представленный образец», так и информация о точном месте начала (или начал, если их несколько) совпадения подстроки с образцом. Назовём образцом искомую строку, а подстрокой — массив для индексов таких что , где — длина строки, а — сама строка. Также введём образец как .

Простой (наивный) поиск

Суть алгоритма простого поиска состоит в последовательном переборе с последующим сравнением символов строки и образца. Для этого достаточно выполнить следующей алгоритм:

Здесь намеренно не приводится ограничений на правую границу внешнего цикла, т.к. сути алгоритма это не меняет. В общем легко посчитать, что сложность такого поиска будет , где — длина строки , а — образца .

Алгоритм Рабина — Карпа

Этот алгоритм старается уменьшить количество проверок во внутренним цикле простого поиска за счёт использования хэш-функции.

Понятие хэш-функции

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

Например, у нас есть множество целых чисел от 0 до 1 000 000 и ограничение на значение хэш-функции в 10 битов. 10 битов это доступных значений функции. Существуют различные способы написать такую функцию, например:

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

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

Для работы алгоритма необходимо написать хэш-функцию для заданной строки. Если пронумеровать символы алфавита из которых состоит строка, то можно написать тривиальный скользящий хэш, представляющий из себя сумму индексов каждого символа. Например, когда задан алфавит , а символы имеют индексы от 1 до 4, то для строки ACDDAB будем иметь, что 1 + 3 + 4 + 4 + 1 + 2 = 15.

При сдвиге образца на один символ значение хэш-функции для подстроки будет меняться как «минус предыдущий элемент, плюс следующий». Заранее посчитав значение хэш-функции для образца и пользуясь предложенной хэш-функцией при сдвиге образца, мы каждый раз сравниваем сами значения получаемых хэш-функций. Если они совпадают, то нам нужно уже проверить строки посимвольно и, если они полностью совпали, то ответ получен (сравнивать необходимо из-за возможности коллизий):

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

Алгоритм Бойера — Мура

Идея этого алгоритма заключается в том, что строки можно сравнивать с конца. Это позволит пропускать не 1 символ как в наивном алгоритме, но зачастую сразу всю строку. Это возможно, поскольку в тот момент, когда обнаруживается несовпадающий символ между строкой и образцом, то образец необходимо сдвинуть вправо на столько символов, чтобы несовпадающий символ строки теперь совпал с символом образца. Если такого символа в образце нет, то строка сдвигается полностью.

Начиная проверку с конца к началу определяем, что не совпадают символы «в» и «т». Сдвиг, величина шага которого зависит от таблицы, описанную позже, в этом случае будет равен 3:

Снова проверяем сконца: после совпадения «т» в обеих строках не совпадают «д» и «о». Снова сдвигаем, шаг в этом случае равен 3:

В данном примере все символы совпадают, поэтому алгоритм останавливается. Теперь определим, каким образом определяется величина шага для каждого символа. Поскольку суть алгоритма в том, чтобы при несовпадении символа мы двигали образец вправо до тех пор, пока этот символ не совпадёт с символом образца:

Для составления таблицы используется следующее правило: значение для символа равно максимальному индексу этого элемента в образце (исключая последний символ, для него и всех других значение равно количеству символов в образце). Так для строки «данные» это будет:

Тогда величина сдвига при сравнении справа налево и при не совпадении символа на j-ой позиции, где сам символ , будет равна . Приведём алгоритм с приведённой эвристикой, называемой эвристикой стоп-символа:

Эффективность поиска в таком алгоритме достигает

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

Последний из рассматриваемых алгоритмов и являющимся самым эффективным, т.к. работает за линейное время. Основой алгоритма является определение префикс-функции. Префикс-функция вычисляет длину наибольшего собственного (т.е. не равного самой подстроке) префикса совпадающего с суффиксом этой подстроки. Так, для строки котокот префикс «кот» совпадает с суффиксом и длина его равна 3.

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

Таким образом задача сводится к заполнению таблицы вида:

Для решения задачи поиска подстроки достаточно склеить образец и строку с помощью символа, который не входит в алфавит, напр.: P + ‘#’ + S, после чего начать считать префикс-функцию. Как только значение функции будет равно длине образца, то это будет означать, что подстрока найдена:

Источник

Строки (Руководство по программированию на C#)

Сравнение строки и System.String

Объявление и инициализация строк

Вы можете объявлять и инициализировать строки различными способами, как показано в следующем примере:

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

Инициализируйте строку с константным значением Empty для создания нового объекта String, строка которого имеет нулевую длину. Представлением строкового литерала строки с нулевой длиной является «». Если вы инициализируете строки со значением Empty вместо NULL, вы снизите вероятность появления исключения NullReferenceException. Используйте статический метод IsNullOrEmpty(String), чтобы проверить значение строки, прежде чем пытаться получить к ней доступ.

Неизменность строковых объектов

Так как «изменение» строки на самом деле является созданием новой строки, создавать ссылки на строки следует с осторожностью. Если вы создадите ссылку на строку, а затем «измените» исходную строку, ссылка будет по-прежнему указывать на исходный объект, а не на новый объект, который был создан при изменении строки. Это поведение проиллюстрировано в следующем коде:

Сведения о создании новых строк, основанных на таких изменениях, как операции поиска и замены исходной строки, см. в инструкциях по изменению содержимого строки.

Регулярные и буквальные строковые литералы

Используйте регулярные строковые литералы, когда вам нужно внедрить escape-символы, доступные в C#, как показано в следующем примере:

Буквальные строковые литералы используются для удобства и читабельности, если текст строки содержит символы обратной косой черты, например в путях к файлам. Так как буквальные строки сохраняют символы новой строки как часть текста строки, их можно использовать для инициализации многострочных строк. Используйте двойные кавычки, чтобы вставить кавычки в буквальной строке. В следующем примере показаны наиболее часто используемым буквальные строки:

Escape-последовательности строк

Если вы используете escape-последовательность \x с менее чем четырьмя шестнадцатеричными цифрами, то когда непосредственно следующие за ней символы также являются допустимыми шестнадцатеричными цифрами (т. е. 0–9, A–F и a–f), они будут интерпретированы как часть этой escape-последовательности. Например, \xA1 дает результат «¡», являющийся кодовой точкой U+00A1. Однако если следующий символ — «A» или «a», тогда escape-последовательность будет интерпретироваться как \xA1A и даст результат «ਚ», являющийся кодовой точкой U+0A1A. В таких случаях, чтобы избежать некорректной интерпретации, указывайте все четыре шестнадцатеричных знака (например, \x00A1 ).

Во время компиляции буквальные строки преобразуются в обычные строки с теми же escape-последовательностями. Поэтому, если вы просматриваете буквальную строку в окне контрольных значений отладчика, вы увидите escape-символы, добавленные компилятором, а не буквальную версию из исходного кода. Например, буквальная строка @»C:\files.txt» будет отображаться в окне контрольных значений как «C:\\files.txt».

Строки формата

Строка формата — это строка, содержимое которой можно определить динамически во время выполнения. Строки формата создаются путем внедрения интерполированных выражений или заполнителей внутри фигурных скобок в строке. Весь код внутри фигурных скобок ( <. >) будет преобразован в значение и выходные данные как отформатированная строка во время выполнения. Существует два способа создания строк формата: интерполяция строк и составное форматирование.

Интерполяция строк

Начиная с C# 10, можно использовать интерполяцию строк для инициализации константной строки, если все выражения, используемые для заполнителей, также являются константными строками.

Составное форматирование

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

Подстроки

Подстрока — это последовательность символов, содержащихся в строке. Используйте метод Substring, чтобы создать новую строку из части исходной строки. Одно вхождение подстроки или несколько можно найти с помощью метода IndexOf. Используйте метод Replace, чтобы заменить все вхождения указанной подстроки новой строкой. Как и метод Substring, метод Replace фактически возвращает новую строку и не изменяет исходную строку. См. дополнительные сведения о поиске строк и изменении содержимого строк.

Доступ к отдельным символам

Используя нотацию массива со значением индекса, можно получить доступ только для чтения к отдельным символам, как показано в следующем примере:

Если вам необходимо изменить отдельные символы в строке и функций методов String вам недостаточно, используйте объект StringBuilder, чтобы изменить отдельные символы «на месте», а затем создайте новую строку для сохранения результатов с помощью методов StringBuilder. В следующем примере предположим, что необходимо определенным образом изменить исходную строку, а затем сохранить результаты для дальнейшего использования:

Строки NULL и пустые строки

Пустая строка — это экземпляр объекта System.String, который содержит нуль символов. Пустые строки часто используются в различных сценариях программирования для представления пустого текстового поля. Вы можете вызывать методы для пустых строк, так как они являются допустимыми объектами System.String. Пустые строки инициализируются следующим образом:

В отличие от пустых строк строка NULL не ссылается на экземпляр объекта System.String, поэтому любая попытка вызвать метод для строки NULL приводит к исключению NullReferenceException. Но вы можете использовать строки NULL в операциях объединения и сравнения с другими строками. В следующих примерах показаны случаи, в которых ссылка на строку NULL вызывает и не вызывает исключение:

Использование класса StringBuilder для быстрого создания строк

В этом примере объект StringBuilder используется для создания строки из набора числовых типов:

Строки, методы расширения и LINQ

Источник