Алгоритм для поиска вхождения строки p в строку t (с точностью до одного несовпадения)

Question

Написал КПМ (Алгоритм для поиска вхождения строки p в строку t), которая решает задачу, но не с точностью до одного несовпадения символа, не понимаю какую модификацию добавить, чтобы решал с точностью до одного несовпадения символа.

def prefix_function(s):
    n = len(s)
    prefix = [0] * n

    for i in range(1, n):
        j = prefix[i - 1]
        while j > 0 and s[i] != s[j]:
            j = prefix[j - 1]
        if s[i] == s[j]:
            j += 1
        prefix[i] = j

    return prefix

def KMP(pattern, text):
    p_size = len(pattern)
    t_size = len(text)
    combined = pattern + '#' + text
    prefix = prefix_function(combined)
    result = []

    for i in range(p_size + 1, p_size + 1 + t_size):
        if prefix[i] == p_size:
            result.append(i - p_size * 2)

    return result

p = input().strip()
t = input().strip()

res = KMP(p, t)

print(len(res))
if res:
    print(' '.join(map(str, res)))

Answer 1

Создайте строку

f = p + "#" + t

где "#" - символ, который не встрeчается в теле строк.

Посчитайте для f z-функцию - это массив длин максимального префикса подстроки, начинающейся с позиции x в строке f, который одновременно является и префиксом всей строки f

Если вы встретили в массиве z[] значение, равное lp=len(p) - нашли точное вхождение строки.

Теперь про единичное несовпадение - создайте аналогично объединение перевёрнутых строк

b = rev(p) + "#" + rev(t)

Когда вы встречаете в z(f) ненулевое значение k < lp, то проверяйте в z(b) наличие на соответствующей позиции значения lp-k-1 - если есть, то вы нашли совпадение типа qprs?tu.

Кроме того, для обнаружения несовпадения первого символа придётся z(b) проверить на наличие значений lp-1.

Cобственно, можно эти этапы объединить, и соотносить все, в т.ч. и нулевые значения из z(f)

Время линейное - видимо, это подразумевается, когда дают входные размеры 10^6. То же самое можно сделать и с префикс-функцией, которая у вас уже имеется (строки наоборот объединять и ещё чего чуть поправить)

Что получаeтся:

def z_function(s):
    n = len(s)
    z = [0]*n
    l = 0
    r = 0
    for i in range(1, n):
        if (i <= r):
            z[i] = min (r-i+1, z[i-l])
        while (i+z[i] < n) and (s[z[i]] == s[i+z[i]]):
            z[i] += 1
        if (i+z[i]-1 > r):
            l = i
            r = i+z[i]-1
    return z

t = 'caaabdaaaasdacaa'
lt = len(t)
p = 'aaaa'
lp = len(p)
f = p + '#' + t
zf = z_function(f)
b = p[::-1] + "#" + t[::-1]
zb = z_function(b)
print(*[(i+10-lp)%10 for i in range(lt + lp + 1)])
print(" ".join(f))
print(*zf)
print(" ".join(b))
print(*zb)
for i in range(lt-lp+1):
    if zf[i + lp + 1] == lp:
        print('exact match:', i + 1)
    elif zf[i + lp + 1] + zb[lt + 1 - i] == lp-1:
       print('one-mismatch:', i + 1)

6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6  #просто линейка, позиция в t
a a a a # c a a a b d a a a a s d a c a a  #f 
0 3 2 1 0 0 3 2 1 0 0 4 3 2 1 0 0 1 0 2 1  #zf
a a a a # a a c a d s a a a a d b a a a c  #b
0 3 2 1 0 2 1 0 1 0 0 4 3 2 1 0 0 3 2 1 0  #zb

one-mismatch: 1
one-mismatch: 2
one-mismatch: 6
exact match: 7
one-mismatch: 8
one-mismatch: 13

БЛОГ НА HUSL

Алгоритм для поиска вхождения строки p в строку t (с точностью до одного несовпадения)

Ответы (1 шт):