m4lvx

Search

SearchSearch

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

Jun 08, 20243 min read

Что такое префикс-функция

Префикс-функция строки используется в алгоритмах обработки строк, таких как алгоритм Кнута-Морриса-Пратта (KMP) для поиска подстрок. Префикс-функция для строки s длины n определяет массив pi, где pi[i] — это длина наибольшего собственного префикса строки s[0...i], который также является суффиксом этой подстроки.

Пример

Для строки “ababcab”:

Префикс-функция: [0, 0, 1, 2, 0, 1, 2]

  • pi[0] = 0, так как первый символ не имеет собственного префикса.
  • pi[1] = 0, так как префикс строки “ab” не совпадает с суффиксом.
  • pi[2] = 1, так как префикс “a” совпадает с суффиксом “a”.
  • pi[3] = 2, так как префикс “ab” совпадает с суффиксом “ab”.
  • pi[4] = 0, так как нет совпадающего префикса и суффикса для “ababc”.
  • pi[5] = 1, так как префикс “a” совпадает с суффиксом “a”.
  • pi[6] = 2, так как префикс “ab” совпадает с суффиксом “ab”.

Наивная реализация

Наивная реализация префикс-функции включает в себя двойной цикл для проверки всех возможных префиксов и суффиксов для каждой позиции.

Алгоритм:

  1. Создаем массив pi длиной n и инициализируем его нулями.
  2. Для каждой позиции i от 1 до n-1: 3. Ищем наибольший суффикс, который также является префиксом для подстроки s[0...i]. 4. Сохраняем длину этого суффикса в pi[i].

Код на C++:

#include <iostream>
#include <vector>
#include <string>
 
std::vector<int> naivePrefixFunction(const std::string &s) {
    int n = s.length();
    std::vector<int> pi(n, 0);
 
    for (int i = 1; i < n; i++) {
        for (int k = i; k > 0; k--) {
            if (s.substr(0, k) == s.substr(i - k + 1, k)) {
                pi[i] = k;
                break;
            }
        }
    }
 
    return pi;
}
 
int main() {
    std::string s = "ababcab";
    std::vector<int> pi = naivePrefixFunction(s);
 
    for (int p : pi) {
        std::cout << p << " ";
    }
    return 0;
}

Эффективная реализация

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

Алгоритм:

  1. Создаем массив pi длиной n и инициализируем его нулями.
  2. Проходим по строке с 1 до n-1: 3. Используем значение pi[k-1] для ускорения поиска длины наибольшего суффикса, совпадающего с префиксом. 4. Если символы совпадают, увеличиваем значение pi[i].

Код на C++:

#include <iostream>
#include <vector>
#include <string>
 
std::vector<int> efficientPrefixFunction(const std::string &s) {
    int n = s.length();
    std::vector<int> pi(n, 0);
 
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        pi[i] = j;
    }
 
    return pi;
}
 
int main() {
    std::string s = "ababcab";
    std::vector<int> pi = efficientPrefixFunction(s);
 
    for (int p : pi) {
        std::cout << p << " ";
    }
    return 0;
}

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

Graph View

Backlinks