Z-алгоритм для поиска подстроки в строке. Код написан AI , но мне пришлось немного обучить его правильному синтаксису FB:
Код
' Функция для вычисления Z-массива (zArray) для данного паттерна.
Sub computeZArray(pattern As String, patternLength As Integer, zArray() As Integer)
' Инициализация переменных для указателей левого и правого концов.
Dim iLeft As Integer = 0
Dim iRight As Integer = 0
' Проход по всем символам паттерна, начиная с 1 (не включая начало).
For i As Integer = 1 To patternLength - 1
If i > iRight Then
' Обновляем правый указатель и левый указатель.
iRight = i
iLeft = iRight
' Вычисление Z-значения для текущего символа.
While iRight < patternLength Andalso _
pattern[iRight - iLeft] = pattern[iRight]
iRight += 1
Wend
zArray(i) = iRight - iLeft
iRight -= 1
Else
' Вычисление индекса k для сравнения.
Dim k As Integer = i - iLeft
If zArray(k) < iRight - i + 1 Then
' Используем уже вычисленное значение Z.
zArray(i) = zArray(k)
Else
' Обновляем левый и правый указатели для нового Z-значения.
iLeft = i
While iRight < patternLength Andalso _
pattern[iRight - iLeft] = pattern[iRight]
iRight += 1
Wend
zArray(i) = iRight - iLeft
iRight -= 1
End If
End If
Next
End Sub
' Функция для поиска подстроки в тексте.
Function findSubstring(startPosition As Integer, text As String, pattern As String) As Integer
' Получение длины текста и паттерна.
Dim textLength As Integer = Len(text)
Dim patternLength As Integer = Len(pattern)
If patternLength = 0 Then Return -1
If startPosition < 0 Or startPosition >= textLength Then Return -1
' Создание объединенной строки с паттерном и разделителем.
Dim combined As String = pattern + "$"
combined += Mid(text, startPosition + 1)
' Выделение памяти для Z-массива.
Dim zArray(Len(combined)) As Integer
computeZArray(combined, Len(combined), zArray())
' Проход по Z-массиву для нахождения индекса подстроки.
For i As Integer = patternLength + 1 To Len(combined) - 1
If zArray(i) = patternLength Then
Return startPosition + (i - patternLength - 1)
End If
Next
Return -1
End Function
' Инициализация переменных для текста, паттерна и начальной позиции.
Dim text As String = "hello world, hello universe"
Dim pattern As String = "hello"
Dim startPosition As Integer = 1
' Поиск подстроки в тексте.
Dim index As Integer = findSubstring(startPosition, text, pattern)
If index <> -1 Then
Print "Pattern found at index: "; index
Else
Print "Pattern not found"
End If
А это описание от AI для данного кода:
Цитата
Алгоритм работы данного кода основан на использовании Z-алгоритма для поиска подстроки в тексте. Вот шаги, которые выполняет программа:
Инициализация:
Определяются переменные iLeft и iRight, используемые для отслеживания текущего сегмента строки, в котором мы ищем совпадения с паттерном.
Вычисление Z-массива:
Для каждого символа в паттерне (кроме первого), если текущий индекс i находится вне текущего сегмента совпадения (i > iRight), то мы начинаем новый поиск.
Обновляем iRight и iLeft, чтобы указать на начало потенциального совпадения.
Проходим по строке, сравнивая символы до тех пор, пока не встретим различие или не достигнем конца паттерна.
Записываем длину найденного совпадения (Z-значение) в массив zArray.
Поиск подстроки:
Создаем новую строку, объединяя паттерн с текстом, разделенных специальным символом $.
Вызываем функцию computeZArray для вычисления Z-массива для этой новой строки.
Проходим по массиву zArray, чтобы найти индекс в тексте, где начинается паттерн.
Если Z-значение равно длине паттерна, значит, подстрока найдена. Возвращаем индекс начала подстроки в исходном тексте.
Основная программа:
Инициализируем переменные для текста и паттерна.
Вызываем функцию findSubstring с заданными параметрами.
Если подстрока найдена, выводим сообщение с ее индексом; в противном случае выводим сообщение о том, что подстрока не найдена.
Таким образом, программа использует Z-алгоритм для эффективного поиска паттерна в тексте, предоставляя возможность определить позицию первого вхождения паттерна в случае успеха.
