Как найти все вхождения подстроки в строку - Исправление недочетов и поиск решений вместе с Examum.ru

Many times while working with strings, we have problems dealing with substrings. This may include the problem of finding all positions of a particular substrings in a string. Let’s discuss certain ways in which this task can be performed.

Method #1 : Using list comprehension + startswith() This task can be performed using the two functionalities. The startswith function primarily performs the task of getting the starting indices of substring and list comprehension is used to iterate through the whole target string.

Python3

test_str = "GeeksforGeeks is best for Geeks"

test_sub = "Geeks"

print("The original string is : " + test_str)

print("The substring to find : " + test_sub)

res = [i for i in range(len(test_str)) if test_str.startswith(test_sub, i)]

print("The start indices of the substrings are : " + str(res))

Output :

The original string is : GeeksforGeeks is best for Geeks
The substring to find : Geeks
The start indices of the substrings are : [0, 8, 26]

Time Complexity: O(n*m), where n is the length of the original string and m is the length of the substring to find
Auxiliary Space: O(k), where k is the number of occurrences of the substring in the string

Method #2 : Using re.finditer() The finditer function of the regex library can help us perform the task of finding the occurrences of the substring in the target string and the start function can return the resultant index of each of them.

Python3

import re

test_str = "GeeksforGeeks is best for Geeks"

test_sub = "Geeks"

print("The original string is : " + test_str)

print("The substring to find : " + test_sub)

res = [i.start() for i in re.finditer(test_sub, test_str)]

print("The start indices of the substrings are : " + str(res))

Output :

The original string is : GeeksforGeeks is best for Geeks
The substring to find : Geeks
The start indices of the substrings are : [0, 8, 26]

Method #3 : Using find() and replace() methods

Python3

test_str = "GeeksforGeeks is best for Geeks"

test_sub = "Geeks"

print("The original string is : " + test_str)

print("The substring to find : " + test_sub)

res=[]

while(test_str.find(test_sub)!=-1):

res.append(test_str.find(test_sub))

test_str=test_str.replace(test_sub,"*"*len(test_sub),1)

print("The start indices of the substrings are : " + str(res))

Output

The original string is : GeeksforGeeks is best for Geeks
The substring to find : Geeks
The start indices of the substrings are : [0, 8, 26]

Time Complexity: O(n*m), where n is the length of the original string and m is the length of the substring to find.
Auxiliary Space: O(k), where k is the number of occurrences of the substring in the string.

Method #4 : Using find()

The find() method is used to find the index of the first occurrence of the substring in the string. We start searching for the substring from the beginning of the string and continue searching until the substring is not found in the remaining part of the string. If the substring is found, we add its start index to the list of indices and update the start index to start searching for the next occurrence of the substring.

Python3

def find_substring_indices(string, substring):

indices = []

start_index = 0

while True:

index = string.find(substring, start_index)

if index == -1:

break

else:

indices.append(index)

start_index = index + 1

return indices

string = "GeeksforGeeks is best for Geeks"

substring = "Geeks"

indices = find_substring_indices(string, substring)

print("The original string is:", string)

print("The substring to find:", substring)

print("The start indices of the substrings are:", indices)

Output

The original string is: GeeksforGeeks is best for Geeks
The substring to find: Geeks
The start indices of the substrings are: [0, 8, 26]

Time complexity: O(nm)
Auxiliary space: O(1)

Method #5: Using string slicing and while loop

Initialize an empty list to store the indices of all occurrences of the substring.
Set the starting index i to 0.
Use a while loop to keep searching for the substring in the string.
Inside the while loop, use the find() method to find the first occurrence of the substring in the string, starting from the current index i.
If find() returns -1, it means that there are no more occurrences of the substring in the string, so break out of the loop.
If find() returns a non-negative value, append the index of the first character of the substring to the list, and update the starting index i to the next character after the end of the substring.
Repeat steps 4-6 until there are no more occurrences of the substring in the string.
Return the list of indices.

Python3

def find_all_substrings(string, substring):

indices = []

i = 0

while i < len(string):

j = string.find(substring, i)

if j == -1:

break

indices.append(j)

i = j + len(substring)

return indices

test_str = "GeeksforGeeks is best for Geeks"

test_sub = "Geeks"

print(find_all_substrings(test_str, test_sub))

Time complexity: O(nm), where n is the length of the string and m is the length of the substring.
Auxiliary space: O(k), where k is the number of occurrences of the substring in the string.

Method #6 : Using re.finditer() and reduce():

Algorithm:

1. Import the required modules – re and functools.
2.Initialize the input string test_str and the substring to be searched test_sub.
3.Use re.finditer() to find all the occurrences of the substring test_sub in the string test_str.
4. Use reduce() to get the start indices of all the occurrences found in step 3.
5. The lambda function inside the reduce() takes two arguments – the first one is the list x that accumulates the start 6.indices and the second one is the Match object y returned by finditer(). The function adds the start index of the 7.current Match object to the list x.
8. Convert the final result to a string and print it.

Python3

import re

from functools import reduce

test_str = "GeeksforGeeks is best for Geeks"

test_sub = "Geeks"

occurrences = re.finditer(test_sub, test_str)

res = reduce(lambda x, y: x + [y.start()], occurrences, [])

print("The start indices of the substrings are : " + str(res))

Output

The start indices of the substrings are : [0, 8, 26]

Time Complexity: O(n), where n is the length of the input string.

Auxiliary Space: O(m), where m is the number of occurrences of the substring in the input string. This is because we need to store the start indices of all the occurrences in a list.

Last Updated :
03 May, 2023

Like Article

Save Article

Источник

Используйте функцию string.count() для поиска всех вхождений подстроки в строке в Python
Используйте понимание списка и startswith(), чтобы найти все вхождения подстроки в строке в Python
Используйте re.finditer(), чтобы найти все вхождения подстроки в строке в Python

Python: найти все вхождения в строке

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

В этом руководстве будут рассмотрены различные методы поиска всех вхождений подстроки в строке в Python.

Используйте функцию `string.count()` для поиска всех вхождений подстроки в строке в Python

string.count() — это встроенная функция в Python, которая возвращает количество или количество вхождений подстроки в данной конкретной строке. Кроме того, в нем есть дополнительные параметры start и end для указания индексов начальной и конечной позиций.

Метод count() просматривает строку и возвращает количество раз, когда определенная подстрока встречалась в строке.

Следующий код использует функцию string.count() для поиска всех вхождений подстроки в строку.

#defining string and substring
str1 = "This dress looks good; you have good taste in clothes."
substr = "good"

#occurrence of word 'good' in whole string
count1 = str1.count(substr)
print(count1)

#occurrence of word 'good' from index 0 to 25
count2 = str1.count(substr,0,25)
print(count2)

Выход:

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

Используйте понимание списка и `startswith()`, чтобы найти все вхождения подстроки в строке в Python

Этому методу нужны две вещи: понимание списка и метод startswith().

Функция startswith() выполняет задачу получения начальных индексов подстроки, а понимание списка используется для итерации по всей целевой строке.

Следующий код использует понимание списка и startswith() для поиска всех вхождений подстроки в строку.

# defining string 
str1 = "This dress looks good; you have good taste in clothes."
  
# defining substring
substr = "good"
  
# printing original string 
print("The original string is : " + str1)
  
# printing substring 
print("The substring to find : " + substr)
  
# using list comprehension + startswith()
# All occurrences of substring in string 
res = [i for i in range(len(str1)) if str1.startswith(substr, i)]
  
# printing result 
print("The start indices of the substrings are : " + str(res))

Выход:

The original string is : This dress looks good; you have good taste in clothes.
The substring to find : good
The start indices of the substrings are : [17, 34]

Используйте `re.finditer()`, чтобы найти все вхождения подстроки в строке в Python

re.finditer() — это функция библиотеки регулярных выражений, которую Python предоставляет программистам для использования в своем коде. Это помогает в выполнении задачи поиска вхождения определенного шаблона в строке. Чтобы использовать эту функцию, нам нужно сначала импортировать библиотеку регулярных выражений re.

re.finditer() использует в своем синтаксисе параметры pattern иstring. В этом случае шаблон относится к подстроке.

Следующий код использует функцию re.finditer() для поиска всех вхождений подстроки в строку.

import re 
 
# defining string  
str1 = "This dress looks good; you have good taste in clothes."
 
#defining substring 
substr = "good"
 
print("The original string is: " + str1) 
 
print("The substring to find: " + substr) 
 
result = [_.start() for _ in re.finditer(substr, str1)] 
 
print("The start indices of the substrings are : " + str(result))

Выход:

The original string is: This dress looks good; you have good taste in clothes.
The substring to find: good
The start indices of the substrings are : [17, 34]

Источник

Поиск подстроки и смежные вопросы

Время на прочтение
13 мин

Количество просмотров 112K

Здравствуйте, уважаемое сообщество! Недавно на Хабре проскакивала неплохая обзорная статья о разных алгоритмах поиска подстроки в строке. К сожалению, там отсутствовали подробные описания каких либо из упомянутых алгоритмов. Я решил восполнить данный пробел и описать хотя бы парочку тех, которые потенциально можно запомнить. Те, кто еще помнит курс алгоритмов из института, не найдут, видимо, ничего нового для себя.

Сначала хотел бы предотвратить вопрос «на кой это надо? все уже и так написано». Да, написано. Но во-первых, полезно знать как работает используемые тобой иструменты на более низком уровне чтобы лучше понимать их ограничения, а во-вторых, есть достаточно большие смежные области, где работающей из коробочки функции strstr() окажется недостаточно. Ну и в-третьих, вам может неповезти и придется разрабатывать под мобильную платформу с неполноценным runtime, а тогда лучше знать на что подписываетесь, если решитесь самостоятельно его дополнять (чтобы убедиться, что это не сферическая проблема в вакууме, достаточно попробовать wcslen() и wcsstr() из Android NDK).

А разве просто поискать нельзя?

Дело в том, что очевидный способ, который все формулирует как «взять и поискать», является отнюдь не самым эффективным, а для такой низкоуровневой и сравнительно частовызываемой функции это немаловажно. Итак, план такой:

Постановка задачи: здесь перечислены определения и условные обозначения.
Решение «в лоб»: здесь будет описано, как делать не надо и почему.
Z-функция: простейший вариант правильной реализации поиска подстроки.
Алгоритм Кнута-Морриса-Пратта: еще один вариант правильного поиска.
Другие задачи поиска: вкратце пробегусь по ним без подробного описания.

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

Канонический вариант задачи выглядит так: есть у нас строка A (текст). Необходимо проверить, есть ли в ней подстрока X (образец), и если есть, то где она начинается. То есть именно то, что делает функция strstr() в C. Дополнительно к этому можно еще попросить найти все вхождения образца. Очевидно, что задача имеет смысл только если X не длинее A.
Для простоты дальнейшего объяснения введу сразу пару понятий. Что такое строка все, наверное, понимают — это последовательность символов, возможно пустая. Символы, или буквы, принадлежат некоторому множеству, которое называют алфавитом (данный алфавит, вообще говоря, может не иметь ничего общего с алфавитом в бытовом понимании). Длина строки |A| — это, очевидно, количество символов в ней. Префикс строки A[..i] — это строка из i первых символов строки A. Суффикс строки A[j..] — это строка из |A|-j+1 последних символов. Подстроку из A будем обозначать как A[i..j], а A[i] — i-ый символ строки. Вопрос про пустые суффиксы и префиксы и т.д. не трогаем — с ними разобраться не сложно по месту. Еще есть такое понятие как сентинел — некий уникальный символ, не встречающийся в алфавите. Его обозначают значком $ и дополняют допустимый алфавит таким символом (это в теории, на практике проще применить дополнительные проверки, чем придумать такой символ, которого не могло бы оказаться во входных строках).
В выкладках будем считать символы в строке с первой позиции. Код писать традиционно проще отсчитывая от нуля. Переход от одного к другому не составляет трудностей.

Решение «в лоб»

Прямой поиск, или, как еще часто говорят, «просто взять и поискать»- это Первое решение, которое приходит в голову неискушенному программисту. Суть проста: идти по проверяемой строке A и искать в ней вхождение первого символа искомой строки X. Когда находим, делаем гипотезу, что это и есть то самое искомое вхождение. Затем остается проверять по очереди все последующие символы шаблона на совпадение с соответствующими символами строки A. Если они все совпали — значит вот оно, прямо перед нами. Но вот если какой-то из символов не совпал, то ничего не остается, как признать нашу гипотезу неверной, что возвращает нас к символу, следующему за вхождением первого символа из X.
Многие люди ошибаются в этом пункте, считая, что не надо возвращаться назад, а можно продолжать обработку строки A с текущей позиции. Почему это не так легко продемонстрировать на примере поиска X=«AAAB» в A=«AAAAB». Первая гипотеза нас приведет к четвертому символу A: «AAAAB», где мы обнаружим несоответствие. Если не откатиться назад, то вхождение мы так и не обнаружим, хотя оно есть.
Неправильные гипотезы неизбежны, а из-за таких откатываний назад при плохом стечении обстоятельств может оказаться, что мы каждый символ в A проверили около |X| раз. То есть вычислительная сложность сложность алгоритма O(|X||A|). Так поиск фразы в параграфе может и затянуться…
Справедливости ради следует отметить, что если строки невелики, то такой алгоритм может работать быстрее «правильных» алгоритмов за счет более предсказуемого с точки зрения процессора поведения.

Z-функция

Одна из категорий правильных способов поиска строки сводится к вычислению в каком-то смысле корреляции двух строк. Сначала отметим, что задача сравнения начал двух строк проста и понятна: сравниваем соответствующие буквы, пока не найдем несоответствие либо какая-нибудь из строк закончится. Рассмотрим множество всех суффиксов строки A: A[|A|..] A[|A|-1..],… A[1..]. Будем сравнивать начало самой строки с каждым из ее суффиксов. Сравнение может дойти до конца суффикса, либо оборваться на каком-то символе ввиду несовпадения. Длину совпавшей части и назовем компонентой Z-функции для данного суффикса.
То есть Z-функция — это вектор длин наибольшего общего префикса строки с ее суффиксом. Ух! Отличная фраза, когда надо кого-то запутать или самоутвердиться, а чтобы понять что же это такое, лучше рассмотреть пример.
Исходная строка «ababcaba». Сравнивая каждый суффикс с самой строкой получим табличку для Z-функции:

суффикс	строка		Z
ababcaba	ababcaba	->	8
babcaba	ababcaba	->	0
abcaba	ababcaba	->	2
bcaba	ababcaba	->	0
caba	ababcaba	->	0
aba	ababcaba	->	3
ba	ababcaba	->	0
a	ababcaba	->	1

Префикс суффикса это ничто иное, как подстрока, а Z-функция — длины подстрок, которые встречаются одновременно в начале и в середине. Рассматривая все значения компонент Z-функции, можно заметить некоторые закономерности. Во-первых, очевидно, что значение Z-функции не превышает длины строки и совпадает с ней только для «полного» суффикса A[1..] (и поэтому это значение нас не интересует — мы его будем опускать в своих рассуждениях). Во-вторых, если в строке есть некий символ в единственном экземпляре, то совпасть он может только с самим собой, и значит он делит строку на две части, а значение Z-функции нигде не может превысить длины более короткой части.
Использовать эти наблюдения предлагается следующим образом. Допустим в строке «ababcabсacab» мы хотим поискать «abca». Берем эти строчки и конкатенируем, вставляя между ними сентинел: «abca$ababcabсacab». Вектор Z-функции выглядит для такой строки так:

a b c a $ a b a b c a b с a c a b

17 0 0 1 0 2 0 4 0 0 4 0 0 1 0 2 0

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

все

позиции вхождения искомой строки (отметьте, что найденные участки расположены внахлест друг с другом, но все-равно наши рассуждения остаются верны).
Ну, значит если мы сможем быстро строить вектор Z-функции, то поиск с его помощью всех вхождений строки сводится к поиску в нем значения ее длины. Вот только если вычислять Z-функцию для каждого суффикса, то будет это явно не быстрее, чем решение «в лоб». Выручает нас то, что значение очередного элемента вектора можно узнать опираясь на предыдущие элементы.
Допустим, мы каким-то образом посчитали значения Z-функции вплоть до соответствующего i-1-ому символу. Рассмотрм некую позицию r<i, где мы уже знаем Z_r.
Значит Z_r символов начиная с этой позиции точно такие же, как и в начале строки. Они образуют так называемый Z-блок. Нас будет интересовать самый правый Z-блок, то-есть тот, кто заканчивается дальше всех (самый первый не в счет). В некоторых случаях самый правый блок может быть нулевой длины (когда никакой из непустых блоков не покрывает i-1, то самым правым будет i-1-ый, даже если Z_i-1= 0).

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

А именно, если мы рассматриваем i-й символ, находящийся в Z_r-блоке, то есть соответствующий символ в начале строки на позиции k=i-r+1. Функция Z_k нам уже известна. Если она меньше, чем оставшееся до конца Z-блока расстояние Z_r-(i-r), то сразу можем быть уверены, что вся область совпадения для этого символа лежит внутри r-того Z-блока и значит результат будет тот же, что и в начале строки: Z_i=Z_k. Если же Z_k >= Z_r-(i-r), то Z_i тоже больше или равна Z_r-(i-r). Чтобы узнать насколько именно она больше, нам надо будет проверять следующие за Z-блоком символы. При этом в случае совпадения h этих символов с соответствующими им в начале строки, Z_i увеличивается на h: Z_i=Z_k + h. В результате у нас может появиться новый самый правый Z-блок (если h>0).

Таким образом, сравнивать символы нам приходится только правее самого правого Z-блока, причем за счет успешных сравнений блок «продвигается» правее, а неуспешные сообщают, что вычисление для данной позиции окончено. Это обеспечивает нам построение всего вектора Z-функции за линейное по длине строки время.
Применив этот алгоритм для поиска подстроки получим сложность по времени O(|A|+|X|), что значительно лучше, чем произведение, которое было в первом варианте. Правда, нам пришлось хранить вектор для Z-функции, на что уйдет дополнительной памяти порядка O(|A|+|X|). На самом деле, если не нужно находить все вхождения, а достаточно только одного, то можно обойтись и O(|X|) памяти, так как длина Z-блока все-равно не может быть больше чем |X|, кроме этого можно не продолжать обработку строки после обнаружения первого вхождения.
Напоследок, пример функции, вычисляющей Z-функцию. Просто модельный вариант без каких либо хитростей.


void z_preprocess(vector<int> & Z, const string & str)
{
        const size_t len = str.size();

        Z.clear();
        Z.resize(len);
        if (0 == len)
                return;

        Z[0] = len;

        for (size_t curr = 1, left = 0, right = 1; curr < len; ++curr)
        {
                if (curr >= right)
                {
                        size_t off = 0;
                        while ( curr + off < len && str[curr + off] == str[off] )
                                ++off;
                        Z[curr] = off;
                        right = curr + Z[curr];
                        left = curr;
                }
                else
                {
                        const size_t equiv = curr - left;
                        if (Z[equiv] < right - curr)
                                Z[curr] = Z[equiv];
                        else
                        {
                                size_t off = 0;
                                while ( right + off < len && str[right - curr + off] == str[right + off] )
                                        ++off;
                                Z[curr] = right - curr + off;
                                right += off;
                                left = curr;
                        }
                }
        }
}

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

Не смотря на логическую простоту предыдущего метода, более популярным является другой алгоритм, который в некотором смысле обратный Z-функции — алгоритм Кнута-Морриса-Пратта (КМП). Введем понятие префикс-функции. Префикс-функция для i-ой позиции — это длина максимального префикса строки, который короче i и который совпадает с суффиксом префикса длины i. Если определение Z-функции не сразило оппонента наповал, то уж этим комбо вам точно удастся поставить его на место А на человеческом языке это выглядит так: берем каждый возможный префикс строки и смотрим самое длинное совпадение начала с концом префикса (не учитывая тривиальное совпадение самого с собой). Вот пример для «ababcaba»:

префикс	префикс	p
a	a	0
ab	ab	0
aba	aba	1
abab	abab	2
ababc	ababc	0
ababca	ababca	1
ababcab	ababcab	2
ababcaba	ababcaba	3

Опять же наблюдаем ряд свойств префикс-функции. Во-первых, значения ограничены сверху своим номером, что следует прямо из определения — длина префикса должна быть больше префикс-функции. Во-вторых, уникальный символ точно так же делит строку на две части и ограничивает максимальное значение префикс-функции длиной меньшей из частей — потому что все, что длиннее, будет содержать уникальный, ничему другому не равный символ.
Отсюда получается интересующий нас вывод. Допустим, мы таки достигли в каком-то элементе этого теоретического потолка. Это значит, что здесь закончился такой префикс, что начальная часть совпадает с конечной и одна из них представляет «полную» половинку. Понятно, что в префиксе полная половинка обязана быть спереди, а значит при таком допущении это должна быть более короткая половинка, максимума же мы достигаем на более длинной половинке.
Таким образом, если мы, как и в предыдущей части, конкатенируем искомую строчку с той, в которой ищем, через сентинел, то точка вхождения длины искомой подстроки в компоненту префикс-функции будет соответствовать месту окончания вхождения. Возьмем наш пример: в строке «ababcabсacab» мы ищем «abca». Конкатенированный вариант «abca$ababcabсacab». Префикс-функция выглядит так:

a b c a $ a b a b c a b с a c a b

0 0 0 1 0 1 2 1 2 3 4 2 3 4 0 1 2

Снова мы нашли все вхождения подстроки одним махом — они оканчиваются на позициях четверок. Осталось понять как же эффективно посчитать эту префикс-функцию. Идея алгоритма незначительно отличается от идеи построения Z-функции.
KMP
Самое первое значение префикс-функции, очевидно, 0. Пусть мы посчитали префикс-функцию до i-ой позиции включительно. Рассмотрим i+1-ый символ. Если значение префикс-функции в i-й позиции P_i, то значит префикс A[..P_i] совпадает с подстрокой A[i-P_i+1..i]. Если символ A[P_i+1] совпадет с A[i+1], то можем спокойно записать, что P_i+1=P_i+1. Но вот если нет, то значение может быть либо меньше, либо такое же. Конечно, при P_i=0 сильно некуда уменьшаться, так что в этом случае P_i+1=0. Допустим, что P_i>0. Тогда есть в строке префикс A[..P_i], который эквивалентен подстроке A[i-P_i+1..i]. Искомая префикс-функция формируется в пределах этих эквивалентных участков плюс обрабатываемый символ, а значит нам можно забыть о всей строке после префикса и оставить только данный префикс и i+1-ый символ — ситуация будет идентичной.
KMP
Задача на данном шаге свелась к задаче для строки с вырезанной серединкой: A[..P_i]A[i+1], которую можно решать рекурсивно таким же способом (хотя хвостовая рекурсия и не рекурсия вовсе, а цикл). То есть если A[P_{P_i}+1] совпадет с A[i+1], то P_i+1=P_{P_i}+1, а иначе снова выкидываем из рассмотрения часть строки и т.д. Повторяем процедуру пока не найдем совпадение либо не дойдем до 0.
KMP
Повторение этих операций должно насторожить — казалось бы получается два вложенных цикла. Но это не так. Дело в том, что вложенный цикл длиной в k итераций уменьшает префикс-функцию в i+1-й позиции хотя бы на k-1, а для того, чтобы нарастить префикс-функцию до такого значения, нужно хотя бы k-1 раз успешно сопоставить буквы, обработав k-1 символов. То есть длина цикла соответствует промежутку между выполнением таких циклов и поэтому сложность алгоритма по прежнему линейна по длине обрабатываемой строки. С памятью тут такая-же ситуация, как и с Z-функцией — линейная по длине строки, но есть способ сэкономить. Кроме этого есть удобный факт, что символы обрабатываются последовательно, то есть мы не обязаны обрабатывать всю строку, если первое вхождение мы уже получили.
Ну и для примера фрагмент кода:


void calc_prefix_function(vector<int> & prefix_func, const string & str)
{
    const size_t str_length = str.size();

    prefix_func.clear();
    prefix_func.resize(str_length);
    if (0 == str_length)
        return;

    prefix_func[0] = 0;

    for (size_t current = 1; current < str_length; ++current)
    {
        size_t matched_prefix = current - 1;
        size_t candidate = prefix_func[matched_prefix];
        while (candidate != 0 && str[current] != str[candidate])
        {
            matched_prefix = prefix_func[matched_prefix] - 1;
            candidate = prefix_func[matched_prefix];
        }

        if (candidate == 0)
            prefix_func[current] = str[current] == str[0] ? 1 : 0;
        else
            prefix_func[current] = candidate + 1;
    }
}

Не смотря на то, что алгоритм более замысловат, реализация его даже проще, чем для Z-функции.

Другие задачи поиска

Дальше пойдет просто много букв о том, что этим задачи поиска строк не ограничиваются и что есть другие задачи и другие способы решения, так что если кому не интересно, то дальше можно не читать. Эта информация просто для ознакомления, чтобы в случае необходимости хотя бы осознавать, что «все уже украдено до нас» и не переизобретать велосипед.
Хоть вышеописанные алгоритмы и гарантируют линейное время выполнения, звание «алгоритма по умолчанию» получил алгоритм Бойера-Мура. В среднем он тоже дает линейное время, но еще и имеет лучше константу при этой линейной функции, но это в среднем. Бывают «плохие» данные, на которых он оказываются не лучше простейшего сравнения «в лоб» (ну прямо как с qsort). Он на редкость запутан и рассматривать его не будем — все-равно не упомнить. Есть еще ряд экзотических алгоритмов, которые ориентированы на обработку текстов на естественном языке и опираются в своих оптимизациях на статистические свойства слов языка.
Ну ладно, есть у нас алгоритм, который так или иначе за O(|X|+|A|) ищет подстроку в строке. А теперь представим, что мы пишем движок для гостевой книги. Есть у нас список запрещенных матерных слов (понятно, что так не поможет, но задача просто для примера). Мы собираемся фильтровать сообщения. Будем каждое из запрещенных слов искать в сообщении и… на это у нас уйдет O(|X₁|+|X₂|+…+|X_n|+n|A|). Как-то так себе, особенно если словарь «могучих выражений» «великого и могучего» очень «могуч». Для этого случая есть способ так предобработать словарь искомых строк, что поиск будет занимать только O(|X₁|+|X₂|+…+|X_n|+|A|), а это может быть существенно меньше, особенно если сообщения длинные.
Такая предобработка сводится к построению бора (trie) из словаря: дерево начинается в некотором фиктивном корне, узлы соответствует буквам слов в словаре, глубина узла дерева соответствует номеру буквы в слове. Узлы, в которых заканчивается слово из словаря называются терминальными и помечены неким образом (красным цветом на рисунке).
Trie
Полученное дерево является аналогом префикс-функции алгоритма КМП. С его помощью можно найти все вхождения всех слов словаря в фразе. Надо идти по дереву, проверяя наличие очередного символа в виде узла дерева, попутно отмечая встречающиеся терминальные вершины — это вхождения слов. Если соответствующего узла в дереве нет, то как и в КМП, происходит откат выше по дереву по специальным ссылкам. Данный алгоритм носит название алгоритма Ахо-Корасика. Такую же схему можно применять для поиска во время ввода и предсказания следующего символа в электронных словарях.
В данном примере построение бора несложно: просто добавляем в бор слова по очереди (нюансы только с дополнительными ссылками для «откатов»). Есть ряд оптимизаций, направленный на сокращение использования памяти этим деревом (т.н. сжатие бора — пропуск участков без ветвлений). На практике эти оптимизации чуть ли не обязательны. Недостатком данного алгоритма является его алфавитозависимость: время на обработку узла и занимаемая память зависят от количества потенциально возможных детей, которое равно размеру алфавита. Для больших алфавитов это серьезная проблема (представляете себе набор символов юникода?). Подробнее про это все можно почитать в этом хабратопике или воспользовавшись гуглояндексом — благо инфы по этомоу вопросу много.
Теперь посмотрим на другую задачу. Если в предыдущей мы знали заранее, что мы должны будем найти в поступающих потом данных, то здесь с точностью до наоборот: нам заранее выдали строчку, в которой будут искать, но что будут искать — неизвестно, а искать будут много. Типичный пример — поисковик. Документ, в котором ищется слово, известен заранее, а вот слова, которые там ищут, сыпятся на ходу. Вопрос, опять же, как вместо O(|X₁|+|X₂|+…+|X_n|+n|A|) получить O(|X₁|+|X₂|+…+|X_n|+|A|)?
Предлагается построить бор, в котором будут все возможные суффиксы имеющейся строки. Тогда поиск шаблона сведется к проверки наличия пути в дереве, соответствующего искомому шаблону. Если строить такой бор перебором всех суффиксов, то эта процедура может занять O(|A|²) времени, да и по памяти много. Но, к счастью, существуют алгоритмы, которые позволяют построить такое дерево сразу в сжатом виде — суффиксное дерево, причем сделать это за O(|A|). Недавно на Хабре была по этому поводу статья, так что интересующиеся могут прочитать про алгоритм Укконена там.
Плохо в суффиксном дереве, как обычно, две вещи: то, что это дерево, и то, что узлы дерева алфавитозависимы. От этих недостатков избавлен суффиксный массив. Суть суффиксного массива заключается в том, что если все суффиксы строки отсортировать, то поиск подстроки сведется к поиску группы расположенных рядом суффиксов по первой букве искомого образца и дальнейшего уточнения диапазона по последующим. При этом сами суффиксы в отсортированном виде хранить незачем, достаточно хранить позиции, в которых они начинаются в исходных данных. Правда, временные зависимости у данной структуры несколько хуже: единичный поиск будет обходиться O(|X| + log|A|) если подумать и сделать все аккуратно, и O(|X|log|A|) если не заморачиваться. Для сравнения в дереве для фиксированного алфавита O(|X|). Но зато то, что это массив, а не дерево, может улучшить ситуацию с кэшированием памяти и облегчить задачу предсказателю переходов процессора. Строится суффиксный массив за линейное время с помощью алгоритма Kärkkäinen-Sanders (уж извините, но плохо представляю как это должно звучать на русском). Нынче это один из самых популярных методов индексирования строк.
Вопросов приближенного поиска строк и анализа степени похожести мы тут касаться не будем совсем — слишком большая область для того, чтобы запихнуть в эту статью. Просто упомяну, что там люди зря хлеб не ели и придумали много всяких подходов, поэтому если столкнетесь с подобной задачей — найдите и почитайте. Весьма возможно такая задача уже решена.

Спасибо тем, кто читал! А тем, кто дочитал досюда, спасибо особенное!

UPD: Добавил ссылку на содержательную статью про бор (он же луч, он же префиксное дерево, он же нагруженное дерево, он же trie).

Источник

Обзор PHP-функций для работы со строками и практическое их применение с учетом кодировки UTF-8.

Количество символов

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

Функция strlen($string) возвращает длину строки, но возвращает неправильный результат если в строке есть кириллица в UTF-8, поэтому нужно использовать mb_strlen().

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';

echo strlen($text); // 105
echo mb_strlen($text); // 59

PHP

Количество символов без пробелов

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
$str = mb_ereg_replace('[s]', '', $text);
echo mb_strlen($str); // 49

PHP

Количество слов с строке

Функция str_word_count() возвращает количество слов в строке, но символы обрамленные пробелами будет считаться за слово, например « — ». Так же функция не работает с UTF-8, как видно в примере:

$text = 'Lorem Ipsum - is simply dummy!';
echo str_word_count($text); // 6

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
echo str_word_count($text); // 1

PHP

Рабочий вариант:

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
$str = preg_replace("/[[:punct:]]/", '', $text);
$str = mb_ereg_replace('[s]+', ' ', $str);
$words = explode(' ', $str);
echo count($words); // 10

PHP

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

$text = 'Съешь ещё - этих 
мягких французских булок, 
да выпей же чаю.';

echo substr_count($text, PHP_EOL); // 2

PHP

Количество букв в строке

$text = 'Съешь ещё этих мягких французских булок, да выпей же чаю.';
echo $str = preg_replace('/[^a-zа-яё]/ui', '', $text);
echo mb_strlen($str); // 46

PHP

Количество цифр в строке

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
$str = preg_replace('/[^0-9]/ui', '', $text);
echo mb_strlen($str); // 0

PHP

Количество знаков препинания

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
$str = preg_replace("/[^[:punct:]]/", '', $text);
echo mb_strlen($str); // 3

PHP

Количество пробелов в строке

Или количество вхождений любого другого символа или подстроки.

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
echo substr_count($text, ' '); // 10

PHP

Количество пробелов в начале строки:

$text = '     Съешь ещё - этих мягких французских булок, да выпей же чаю.';
echo mb_strlen($text) - mb_strlen(ltrim($text, ' ')); // 5

PHP

Количество пробелов в конце строки:

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.   ';
echo mb_strlen($text) - mb_strlen(rtrim($text, ' ')); // 3

PHP

Поиск

Получить количество вхождений подстроки

$text = 'Съешь ещё - этих мягких французских булок, да ещё выпей же чаю.';
echo mb_substr_count($text, 'ещё'); // 2

PHP

Найти позицию первого вхождения подстроки

$text = 'Съешь ещё - этих мягких французских булок, да ещё выпей же чаю.';
echo mb_strpos($text, 'ещё'); // 6

// Без учета регистра:
$text = 'Съешь ещё - этих мягких французских булок, да ещё выпей же чаю.';
echo mb_stripos($text, 'ещё'); // 6

PHP

Найти позицию последнего вхождения подстроки

$text = 'Съешь ещё - этих мягких французских булок, да ещё выпей же чаю.';
echo mb_strrpos($text, 'ещё'); // 46

// Без учета регистра:
$text = 'Съешь ещё - этих мягких французских булок, да ещё выпей же чаю.';
echo mb_strirpos($text, 'ещё'); // 46

PHP

Найти все вхождения подстроки

$text = 'Съешь ещё - этих мягких французских булок, да ещё выпей же чаю.';

$offset = 0;
$allpos = array();
while (($pos = mb_strpos($text, 'ещё', $offset)) !== false) {
	$offset   = $pos + 1;
	$allpos[] = $pos;
}

print_r($allpos); // Array ([0] => 6 [1] => 46)

PHP

Извлечение из текста

Начало строки

Получить первый символ:

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
echo mb_substr($text, 0, 1); // С

PHP

Получить три первых символа:

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
echo mb_substr($text, 0, 3); // Съе

PHP

Получить первое слово:

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
echo mb_strstr($text, ' ', true); // Съешь

PHP

Получить все после первого слова:

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
echo mb_strstr($text, ' ', false); // ещё - этих мягких французских булок, да выпей же чаю.

PHP

Конец строки

Получить последний символ:

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
echo mb_substr($text, -1, 1); // .

PHP

Получить три последних символа:

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
echo mb_substr($text, -1, 3); // аю.

PHP

Получить последнее слово:

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
$array = explode(' ', $text);
echo end($array); // чаю.

PHP

Получить всё до последнего слова:

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
$str = mb_substr($text, 0, mb_strrpos($text, ' '));
echo $str; // Съешь ещё - этих мягких французских булок, да выпей же

PHP

Середина строки

Получить второе слово:

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
$array = explode(' ', $text);
echo $array[1]; // ещё

PHP

Получить текст до дефиса:

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
echo mb_substr($text, 0, mb_strpos($text, ' - ')); // Съешь ещё

PHP

Получить текст после дефиса:

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
$str = mb_substr($text, mb_strpos($text, ' - ') + mb_strlen(' - '), -1);
echo $str; // этих мягких французских булок, да выпей же чаю

PHP

Переносы строк

Получить первую строку:

$text = 'Разнообразный опыт укрепление и развитие структуры требуют 
определения направлений прогрессивного развития! Не следует забывать, 
что постоянный рост и сфера активности в  степени обуславливает создание 
системы обучения кадров? С другой стороны дальнейшее развитие различных 
форм влечет за собой процесс внедрения и модернизации.';

$pos = mb_strpos($text, "n");
$str = trim(mb_substr($text, 0, $pos));
echo $str; // Разнообразный опыт укрепление и развитие структуры требуют 

// или
$lines = explode("n", $text);
echo $lines[0]; // Разнообразный опыт укрепление и развитие структуры требуют

PHP

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

$text = 'Разнообразный опыт укрепление и развитие структуры требуют 
определения направлений прогрессивного развития! Не следует забывать, 
что постоянный рост и сфера активности в  степени обуславливает создание 
системы обучения кадров? С другой стороны дальнейшее развитие различных 
форм влечет за собой процесс внедрения и модернизации.';

$pos = mb_strrpos($text, "n");
$str = trim(mb_substr($text, $pos));
echo $str; // форм влечет за собой процесс внедрения и модернизации.

// или
$lines = explode("n", $text);
echo end($lines); // форм влечет за собой процесс внедрения и модернизации.

PHP

Пилучить символы из ковычек и скобок

$text = ''Съешь' "ещё" «этих» [мягких] (французских) {булок} <да>';

// '...'
preg_match_all("/'(.+?)'/", $text, $matches);
echo $matches[1][0]; // Съешь

// "..."
preg_match_all("/"(.+?)"/", $text, $matches);
echo $matches[1][0]; // ещё

// «...»
preg_match_all("/«(.+?)»/", $text, $matches);
echo $matches[1][0]; // этих

// [...]
preg_match_all("/[(.+?)]/", $text, $matches);
echo $matches[1][0]; // мягких

// (...)
preg_match_all("/((.+?))/", $text, $matches);
echo $matches[1][0]; // французских

// {...}
preg_match_all("/{(.+?)}/", $text, $matches);
echo $matches[1][0]; // булок

// <...>
preg_match_all("/<(.+?)>/", $text, $matches);
echo $matches[1][0]; // да

PHP

Замена в строках

Функция substr_replace($search, $replace, $subject, $count) – заменяет часть строки, также не раотает с кирилицей в кодировке UTF-8, в библиатеке mb_string её нет, поэтому приходится использовать пользовольскую функцию:

if (!function_exists('mb_substr_replace')) {
	function mb_substr_replace($original, $replacement, $position, $length)
	{
		$startString = mb_substr($original, 0, $position, 'UTF-8');
		$endString = mb_substr($original, $position + $length, mb_strlen($original), 'UTF-8');
		$out = $startString . $replacement . $endString;
		return $out;
	}
}

PHP

Заменить первый символ:

$text = 'Съешь ещё - этих мягких французских булок.';
echo mb_substr_replace($text, '!', 0, 1); // !ъешь ещё - этих мягких французских булок.

PHP

Заменить три первых символа:

$text = 'Съешь ещё - этих мягких французских булок.';
echo mb_substr_replace($text, '!!!', 0, 3); // !!!шь ещё - этих мягких французских булок.

PHP

Заменить последний символ:

$text = 'Съешь ещё - этих мягких французских булок.';
echo mb_substr_replace($text, '!', -1, 0); // Съешь ещё - этих мягких французских булок!

PHP

Заменить три последних символа:

$text = 'Съешь ещё - этих мягких французских булок.';
echo mb_substr_replace($text, '!!!', -3, 0); // Съешь ещё - этих мягких французских бул!!!

PHP

Замена символов и слов в строке

Для этой задачи подходит функция str_replace($search, $replace, $subject), которая работает со всеми кодировками.

Заменить пробелы:

$text = 'Съешь ещё - этих мягких французских булок.';
echo str_replace(' ', '-', $text); // Съешь-ещё---этих-мягких-французских-булок.

PHP

Заменить слово:

$text = 'Съешь ещё - этих мягких французских булок.';
echo str_replace('мягких', 'твердых', $text); // Съешь ещё - этих твердых французских булок.

PHP

Заменить всё до дефиса:

$text = 'Съешь ещё - этих мягких французских булок.';

$str = 'Не ешь' . mb_substr($text, mb_strpos($text, ' - '), -1);
echo $str; // Не ешь - этих мягких французских булок

PHP

Заменить всё после дефиса:

$text = 'Съешь ещё - этих мягких французских булок.';

$str = mb_substr($text, 0, mb_strpos($text, ' - ') + 3) . 'печенек';
echo $str; // Съешь ещё - печенек

PHP

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

Добавить строку после 10-го символа:

$text = 'Съешь ещё - этих мягких французских булок.';

$str = mb_substr_replace($text, '!!!', 10, 0);
echo $str; // Съешь ещё !!!- этих мягких французских булок.

PHP

Добавить перед словом:

$text = 'Съешь ещё - этих мягких французских булок.';

$str = str_replace(' ещё ', ' же ещё ', $text); 
echo $str; // Съешь же ещё - этих мягких французских булок.

PHP

Добавить после слова:

$text = 'Съешь ещё - этих мягких французских булок.';
$str = str_replace(' ещё ', ' ещё немного ', $text); 
echo $str; // Съешь ещё немного - этих мягких французских булок.

PHP

Вставить строку между всех символов

Для того чтобы вставить символ между всех символов в строке понадобится функция str_split($string) для пробразавания строки в массив, она также не работает с кирилицей. С версии PHP 7.4 появилась функция mb_str_split(), для более ранних версий:

if (!function_exists('mb_str_split')) {
	function mb_str_split($str, $l = 0) {
		if ($l > 0) {
			$ret = array();
			$len = mb_strlen($str, "UTF-8");
			for ($i = 0; $i < $len; $i += $l) {
				$ret[] = mb_substr($str, $i, $l, "UTF-8");
			}
			return $ret;
		}
		return preg_split("//u", $str, -1, PREG_SPLIT_NO_EMPTY);
	}
}

PHP

$text = 'Съешь ещё - этих мягких французских булок.';

$array = mb_str_split($text);;
$new = implode(' ', $array);
echo $new; // С ъ е ш ь   е щ ё   -   э т и х   м я г к и х   ф р а н ц у з с к и х   б у л о к .

PHP

Дописать строку до нужной длины

Функция str_pad($string, $length, $pad_string, $pad_type) дополняет строку другой строкой до заданной длины.

Версия функции для UTF-8:

if (!function_exists('mb_str_pad')) {
	function mb_str_pad($input, $pad_length, $pad_string = ' ', $pad_type = STR_PAD_RIGHT)
	{
		$diff = strlen($input) - mb_strlen($input);
		return str_pad($input, $pad_length + $diff, $pad_string, $pad_type);
	}
}

PHP

Дописать стркуку слева:

$text = 'Привет Мир';
echo mb_str_pad($text,  20, '-', STR_PAD_LEFT); // ----------Привет Мир

PHP

Дописать строку справа:

$text = 'Привет Мир';
echo mb_str_pad($text,  20, '-', STR_PAD_RIGHT); // Привет Мир----------

PHP

Дописать строку с обеих сторон:

$text = 'Привет Мир';
echo mb_str_pad($text,  20, '-', STR_PAD_BOTH); // -----Привет Мир-----

PHP

Удаление из строк

Удаление в начале строки

Удалить первый символ:

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
$new = mb_substr($text, 1);
echo $new; // ъешь ещё - этих мягких французских булок, да выпей же чаю.

PHP

Удалить первые 3 символа:

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
$new = mb_substr($text, 3);
echo $new; // шь ещё - этих мягких французских булок, да выпей же чаю.

PHP

Удалить первое слово:

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
$new = mb_substr($text, mb_strpos($text, ' '));
echo $new; // ещё - этих мягких французских булок, да выпей же чаю.

PHP

Удаление в конце строки

Удалить последний символ:

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
$new = mb_substr($text, 0, -1);
echo $new; // Съешь ещё - этих мягких французских булок, да выпей же чаю

PHP

Удалить три последних символа:

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
$new = mb_substr($text, 0, -3);
echo $new; // Съешь ещё - этих мягких французских булок, да выпей же ч

PHP

Удалить последнее слово:

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
$new = mb_substr($text, 0, mb_strrpos($text, ' '));
echo $new; // Съешь ещё - этих мягких французских булок, да выпей же

PHP

Удаление подсторк

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
$new = str_replace(' мягких', '', $text);
echo $new; // Съешь ещё - этих французских булок, да выпей же чаю.

PHP

Удалить всё перед сиволом:

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
$new = strstr($text, '-'); 
echo $new; // - этих мягких французских булок, да выпей же чаю.

PHP

Удалить всё после сивола:

$text = 'Съешь ещё - этих мягких французских булок, да выпей же чаю.';
$new = strstr($text, '-', true); 
echo $new; // Съешь ещё

// Второй вариант:
$pos = mb_strpos($text, '-');
$new = mb_substr($text, 0, $pos + 1);
echo $new; // Съешь ещё -

PHP

Источник

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

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

Рассмотрим задачу, которая возникает каждый раз, когда вы делаете ctrl+f:

Есть большой текст (t). Нужно найти все вхождения строки (s) в него.

Наивное решение со сравнением всех подстрок (t) длины (|s|) со строкой (s) работает за (O(|t| cdot |s|)). Если текст большой, то длинные слова в нем искать становится очень долго.

Однако существует множество способов решить эту задачу за (O(|s| + |t|)), два самых распространённых и простых из них: через префикс-функцию и через z-функцию (примечание: не «зи», а «зет»).

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

Определение. Префикс-функцией от строки (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]).

vector<int> slow_prefix_function(string s) {
    int n = (int) s.size();
    vector<int> p(n, 0);
    for (int i = 1; i < n; i++)
        for (int len = 1; len <= i; len++)
            // если префикс длины len равен суффиксу длины len
            if (s.substr(0, len) == s.substr(i - len + 1, len))
                p[i] = len;
    return p;
}

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

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

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

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

string s = "choose";
string t =
    "choose life. choose a job. choose a career. choose a family. choose a fu...";

cout << s + "#" + t << endl;
cout << slow_prefix_function(s + "#" + t) << endl;

choose#choose life. choose a job. choose a career. choose a family. choose a fu...
0000000123456000000012345600000000123456000100000001234560000000000012345600000000

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

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

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

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

aaaaa
01234

abcdef
000000

abacabadava
00101230101

Можно заметить следующую особенность: (p_{i+1}) максимум на единицу превосходит (p_i).

Доказательство. Если есть префикс, равный суффиксу строки (s_{:i+1}), длины (p_{i+1}), то, отбросив последний символ, можно получить правильный суффикс для строки (s_{:i}), длина которого будет ровно на единицу меньше.

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

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

Например, в строке (underbrace{aabaa}toverbrace{aabaa}) выделен максимальный префикс, равный суффиксу: (p_{10} = 5). Если следующий символ равен будет равен (t), то (p_{11} = p_{10} + 1 = 6).

Но что происходит, когда (s_{p_i}neq s_{i+1})? Пусть следующий символ в этом же примере равен не (t), а (b).

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

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

vector<int> prefix_function(string s) {
    int n = (int) s.size();
    vector<int> p(n, 0);
    for (int i = 1; i < n; i++) {
        // префикс функция точно не больше этого значения + 1
        int cur = p[i - 1];
        // уменьшаем cur значение, пока новый символ не сматчится
        while (s[i] != s[cur] && cur > 0)
            cur = p[cur - 1];
        // здесь либо s[i] == s[cur], либо cur == 0
        if (s[i] == s[cur])
            p[i] = cur + 1;
    }
    return p;
}

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

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

Z-функция

Немногого более простая для понимания альтернатива префикс-функции — z-функция.

Z-функция от строки (s) определяется как массив (z), такой что (z_i) равно длине максимальной подстроки, начинающейся с (i)-й позиции, которая равна префиксу (s).

[
underbrace{aba}coverbrace{aba}daba hspace{1em} (z_4 = 3)
]

vector<int> slow_z_function (string s) {
    int n = (int) s.size();
    vector<int> z(n, 0); // z[0] считается не определенным
    for (int i = 1; i < n; i++)
        // если мы не вышли за границу и следующие символы совпадают
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            z[i]++;
    return z;
}

aaaaa
04321

abcdef
000000

abacabadava
00103010101

Z-функцию можно использовать вместо префикс-функции в алгоритме Кнута-Морриса-Пратта — только теперь нужные позиции будут начинаться c (|s|), а не заканчиваться. Осталось только научиться её искать за (O(n)).

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

Будем идти слева направо и хранить z-блок — самую правую подстроку, равную префиксу, которую мы успели обнаружить. Будем обозначать его границы как (l) и (r) включительно.

Пусть мы сейчас хотим найти (z_i), а все предыдущие уже нашли. Новый (i)-й символ может лежать либо правее z-блока, либо внутри него:

Если правее, то мы просто наивно перебором найдем (z_i) (максимальный отрезок, начинающийся с (s_i) и равный префиксу), и объявим его новым z-блоком.
Если (i)-й элемент лежит внутри z-блока, то мы можем посмотреть на значение (z_{i-l}) и использовать его, чтобы инициализировать (z_i) чем-то, возможно, отличным от нуля. Если (z_{i-l}) левее правой границы (z)-блока, то (z_i = z_{i-l}) — больше (z_i) быть не может. Если он упирается в границу, то «обрежем» его до неё и будем увеличивать на единичку.

vector<int> z_function (string s) {
    int n = (int) s.size();
    vector<int> z(n, 0);
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        // если мы уже видели этот символ
        if (i <= r)
            // то мы можем попробовать его инициализировать z[i - l],
            // но не дальше правой границы: там мы уже ничего не знаем
            z[i] = min(r - i + 1, z[i - l]);
        // дальше каждое успешное увеличение z[i] сдвинет z-блок на единицу
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            z[i]++;
        // проверим, правее ли мы текущего z-блока
        if (i + z[i] - 1 > r) {
            r = i + z[i] - 1;
            l = i;
        }
    }
    return z;
}

Асимптотика. В алгоритме мы делаем столько же действий, сколько раз сдвигается правая граница z-блока — а это (O(n)).

Сравнение

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

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

Упражнение 1. Дан массив префикс-функции. Исходная строка не дана. Вычислите за (O(n)) зет-функцию этой строки.

Упражнение 2. Дан массив зет-функции. Исходная строка не дана. Вычислите за (O(n)) префикс-функцию этой строки.

Источник

Python3

Python3

Python3

Method #4 : Using find()

Python3

Python3

Python3

Используйте функцию string.count() для поиска всех вхождений подстроки в строке в Python

Используйте понимание списка и startswith(), чтобы найти все вхождения подстроки в строке в Python

Используйте re.finditer(), чтобы найти все вхождения подстроки в строке в Python

Поиск подстроки и смежные вопросы

А разве просто поискать нельзя?

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

Решение «в лоб»

Z-функция

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

Другие задачи поиска

Количество символов

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

Количество символов без пробелов

Количество слов с строке

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

Количество букв в строке

Количество цифр в строке

Количество знаков препинания

Количество пробелов в строке

Количество пробелов в начале строки:

Количество пробелов в конце строки:

Поиск

Получить количество вхождений подстроки

Найти позицию первого вхождения подстроки

Найти позицию последнего вхождения подстроки

Найти все вхождения подстроки

Извлечение из текста

Начало строки

Получить первый символ:

Получить три первых символа:

Получить первое слово:

Получить все после первого слова:

Конец строки

Получить последний символ:

Получить три последних символа:

Получить последнее слово:

Получить всё до последнего слова:

Середина строки

Получить второе слово:

Получить текст до дефиса:

Получить текст после дефиса:

Переносы строк

Получить первую строку:

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

Пилучить символы из ковычек и скобок

Замена в строках

Заменить первый символ:

Заменить три первых символа:

Заменить последний символ:

Заменить три последних символа:

Замена символов и слов в строке

Заменить пробелы:

Заменить слово:

Заменить всё до дефиса:

Заменить всё после дефиса:

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

Добавить строку после 10-го символа:

Добавить перед словом:

Добавить после слова:

Вставить строку между всех символов

Дописать строку до нужной длины

Дописать стркуку слева:

Дописать строку справа:

Дописать строку с обеих сторон:

Удаление из строк

Удаление в начале строки

Удалить первый символ:

Удалить первые 3 символа:

Удалить первое слово:

Удаление в конце строки

Удалить последний символ:

Удалить три последних символа:

Удалить последнее слово:

Используйте функцию `string.count()` для поиска всех вхождений подстроки в строке в Python

Используйте понимание списка и `startswith()`, чтобы найти все вхождения подстроки в строке в Python

Используйте `re.finditer()`, чтобы найти все вхождения подстроки в строке в Python