Если у нас есть строка A
длины N и строка B
длины M, где M < N, могу ли я быстро вычислить минимальное количество букв, которые мне нужно удалить из строки A
, чтобы строка B
не встречалась как подстрока в A
?
Если у нас крошечная длина строки, эта проблема довольно проста для грубой силы: вы просто перебираете битовую маску от 0
до 2^N
и видите, если B
встречается как подстрока в этой подпоследовательности A
. Однако, когда N может достигать 10 000, а M может достигать 1000, этот алгоритм, очевидно, быстро разваливается. Есть ли более быстрый способ сделать это?
Пример: A = ababaa
B = aba
. Ответ = 1
. При повторном выполнении второго A
в будет abbaa
, который не содержит B
.
Изменить: Пользователь n.m. размещен отличный пример счетчика: aabcc
и abc
. Мы хотим удалить одиночный B
, потому что удаление любых A
или c
создаст другой экземпляр строки abc
.