Поиск строки в C: функции поиска и примеры кода

При поиске строки "c" в тексте с помощью кода, можно использовать различные подходы и алгоритмы. Один из наиболее распространенных и эффективных способов поиска подстроки в строке - это использование алгоритма Кнута-Морриса-Пратта (КМП).

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

def prefix_table(pattern):
    prefix = [0] * len(pattern)
    j = 0
    i = 1

    while i < len(pattern):
        if pattern[i] == pattern[j]:
            j += 1
            prefix[i] = j
            i += 1
        else:
            if j != 0:
                j = prefix[j-1]
            else:
                prefix[i] = 0
                i += 1

    return prefix

def kmp_search(text, pattern):
    prefix = prefix_table(pattern)
    j = 0
    i = 0
    matches = []

    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1
        else:
            if j != 0:
                j = prefix[j-1]
            else:
                i += 1

        if j == len(pattern):
            matches.append(i-j)
            j = prefix[j-1]

    return matches

text = "abacabadabacaba"
pattern = "c"
matches = kmp_search(text, pattern)

print("Искомая строка найдена в позициях:")
for match in matches:
    print(match)

В приведенном примере текст abacabadabacaba является исходной строкой, в которой мы хотим найти подстроку "c". Функция kmp_search использует функцию prefix_table для предобработки подстроки "c" и выполняет поиск в исходной строке. Результаты поиска выводятся на экран.

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