Это алгоритм поиска Кнута-Морриса-Пратта , код которого был написан AI. Заслуга AI довольно большая для этого кода , но все таки мне пришлось ему помогать и немножко исправлять. Но все равно неплохо получилось.
Код
' Функция KmpSearch ищет подстроку subStr в строке mainStr, начиная с позиции iStartPosition.
Function KmpSearch(mainStr As String, subStr As String, iStartPosition As Integer = 1) As Long
Dim i As Integer, j As Integer, cl As Integer
' Проверяем, что mainStr не пустая строка. Если да, возвращаем 0.
If Len(mainStr) = 0 Then
Return 0
Endif
' Получаем длину подстроки subStr.
Dim iLen As Integer = Len(subStr)
' Если subStr пустая, возвращаем 0.
If iLen = 0 Then
Return 0
' Если subStr состоит из одного символа, ищем его в mainStr и возвращаем позицию.
Elseif iLen = 1 Then
For i As Integer = iStartPosition - 1 To Len(mainStr) - 1
If mainStr[i] = subStr[0] Then
Return i + 1
Endif
Next
Return 0
Endif
' Создаем массив lps для хранения длины наибольшего суффикса, который является префиксом.
Dim lps(iLen) As Integer
' Инициализируем переменные.
cl = 0
i = 1
' Заполняем массив lps для подстроки subStr.
While i < iLen
If subStr[i] = subStr[cl] Then
cl += 1
i += 1
Elseif cl <> 0 Then
cl = lps(cl - 1)
Else
i += 1
Endif
Wend
' Заполняем массив lps.
For j As Integer = 0 To iLen - 2
If subStr[j + 1] = subStr[cl] Then
cl += 1
Endif
lps(j) = cl
Next j
' Инициализируем переменные для поиска.
i = iStartPosition - 1
j = 0
' Основной цикл поиска подстроки в строке.
While i < Len(mainStr)
If mainStr[i] = subStr[j] Then
i += 1
j += 1
If j = iLen Then
Return i - iLen + 1
Endif
Elseif j <> 0 Then
j = lps(j - 1)
Else
i += 1
Endif
Wend
' Если подстрока не найдена, возвращаем 0.
Return 0
End Function
' Пример использования функции KmpSearch.
Dim mainStr As String = "DABCD"
Dim subStr As String = "BCD"
Print KmpSearch(mainStr, subStr , 2)
А это описание AI для данного кода:
Цитата
Алгоритм работы функции KmpSearch можно описать следующим образом:
Инициализация: Функция принимает три параметра: mainStr (основная строка), subStr (подстрока) и iStartPosition (начальная позиция для поиска). Если mainStr пуста, функция возвращает 0.
Проверка длины подстроки: Если subStr пустая, функция также возвращает 0. Если subStr состоит из одного символа, функция ищет этот символ в mainStr, начиная с позиции iStartPosition - 1, и возвращает позицию найденного символа или 0, если символ не найден.
Построение массива lps: Создаётся массив lps длиной, равной длине subStr. Этот массив поможет в алгоритме Кнута-Морриса-Пратта (KMP). Функция заполняет этот массив значениями, которые показывают длину наибольшего суффикса, являющегося одновременно и префиксом.
Заполнение массива lps: Для каждого символа в subStr кроме последнего, функция проверяет, совпадает ли текущий символ с символом на позиции cl (количество совпадений). Если символы совпадают, увеличиваем cl. В противном случае, если cl не равно 0, переходим к предыдущему значению lps, хранящемуся в массиве.
Поиск подстроки: Функция снова проходит по mainStr, начиная с позиции iStartPosition - 1. Она использует переменные i и j для отслеживания текущих позиций в mainStr и subStr соответственно. Если символы на этих позициях совпадают, обе позиции увеличиваются. Если j достигает длины subStr, функция возвращает позицию найденного символа в mainStr.
Возврат результата: Если подстрока не найдена, функция возвращает 0.
В целом, данный код реализует алгоритм Кнута-Морриса-Пратта для поиска подстроки в строке. Он использует предварительное построение префикс-функции (массив lps), чтобы оптимизировать процесс поиска, избегая повторных сравнений символов.
