🚀 Эффективное удаление подстроки с помощью КМП

leetcoder, 11-02-2025 ,

189

Ссылка на задачу – 1910. Remove All Occurrences of a Substring.

📌 Описание задачи

Даны две строки s и part. Нужно избавиться от всех вхождений part из s, выполняя следующую операцию:

Найти самое левое вхождение part в s и удалить его
Повторять, пока part больше не встречается в s.

🐢 Анализ наивного решения

Достаточно несложно быстро набросать следующее решение:

impl Solution {
    pub fn remove_occurrences(mut s: String, part: String) -> String {
        let P = part.len();
        while let Some(idx) = s.find(&part) {
            s.replace_range(idx..idx+P, "");
        }
        s
    }
}

Временная сложность такого решения в худшем случае достигает O(N²/P)
(здесь P - длина удаляемого шаблона, N - длина строки).
В реальных же применениях очень часто время будет линейным и алгоритм будет эффективно работать за счёт предельно малых констант в библиотечной реализации find.

Однако же существует возможность честного решения задачи за линейное, даже в худшем случае, время, и мы рассмотрим такой алгоритм.

💡 Идея

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

Обрабатываем строку за один проход, отслеживая соответствие part с помощью автоматного подхода.
Используем стек состояний для быстрого отката, когда найдено полное вхождение part.
Удаление выполняем мгновенно с помощью truncate, избегая лишних сдвигов.

🏗️ Детали подхода

Вычисляем префикс-функцию для part, чтобы оптимизировать поиск подстроки.
Проходим по s в один проход, отслеживая состояние КМП-автомата:
- Если символ совпадает, переходим в следующее состояние.
- Если не совпадает, переходим в предыдущее возможное состояние (определяемое максимальной длиной заматчившегося префикса).
Когда найдено полное вхождение part, мгновенно удаляем его, используя truncate.
Используем стек состояний, чтобы быстро восстановить предыдущее состояние поиска.

⏳ Асимптотика

Временная сложность:
- Построение префикс-функции — O(M).
- Обход s в один проход — O(N).
- Общее время — O(N+M).
Память:
- Таблица для префикс-функции — O(M).
- Хранение результата и промежуточных состояний — O(N).
- Общая память — O(N+M).

📝 Исходный код

impl Solution {
    pub fn remove_occurrences(s: String, part: String) -> String {
        let pattern = part.as_bytes();
        let text = s.as_bytes();
        let p_len = pattern.len();

        // Build the KMP prefix table
        let prefix_table = Self::build_prefix_table(pattern);

        let mut result = Vec::new(); // Processed characters of `s`
        let mut state_stack = Vec::new(); // Tracks KMP states for backtracking
        let mut state = 0; // Initial KMP state

        for &ch in text.iter() {
            state = Self::kmp_next_state(state, ch, &prefix_table, pattern);

            if state == p_len {
                // Remove `part` from the result
                result.truncate(result.len() - p_len + 1);
                state_stack.truncate(state_stack.len() - p_len + 1);

                // Restore previous KMP state
                state = *state_stack.last().unwrap_or(&0);
            } else {
                // Store the character and its corresponding state
                result.push(ch);
                if state > 0 {
                    state_stack.push(state);
                } else {
                    // Optimize state_stack memory usage in this case
                    state_stack.clear();
                }
            }
        }

        String::from_utf8(result).unwrap()
    }

    // Computes the next KMP state transition based on `state` and `char`
    fn kmp_next_state(mut state: usize, ch: u8, prefix_table: &[usize], pattern: &[u8]) -> usize {
        while state > 0 && pattern[state] != ch {
            state = prefix_table[state];
        }
        if pattern[state] == ch {
            state + 1
        } else {
            0
        }
    }

    // Builds the prefix function (partial match table) for the KMP algorithm
    fn build_prefix_table(pattern: &[u8]) -> Vec<usize> {
        let p_len = pattern.len();
        let mut prefix_table = vec![0; p_len + 1];

        for i in 1..p_len {
            prefix_table[i + 1] = Self::kmp_next_state(prefix_table[i], pattern[i], &prefix_table, pattern);
        }

        prefix_table
    }
}

Tags: #rust #algorithms #strings #kmp