П-функция

Оценим сложность поиска подстроки (шаблона) в строке (тексте):

   1 def search(pattern, text):
   2     for i in range(len(text)-len(pattern)):
   3         for j in range(len(pattern)):
   4             if text[i+j] != pattern[j]
   5                 break
   6         else:
   7             return i
   8     return -1

Какое-нибудь ababababc в abababababababab будет крутиться в этом алгоритме ни много, ни мало ~(len(text)/2)**2 оборотов.

Много лишних сравнений!

Π-функция

Решим более общую задачу построения т. н. П-функции (или префикс-функции) для каждой начальной подстроки текста.

Префикс-функция — наибольшая длина начала текста, совпадающего с концом текста (вся строка не в счёт).

Примеры:

• П("ABC") = 0

• П("ABCBA") = 1

• П("ABABAB") = 4

«В лоб» П-функция вычисляется опять-таки квадратично (много лишних сравнений). Но ценой хранения значений префикс-функции для всех начал текста T можно снизить сложность до линейной. Попробуем вычислить П для всех начальных подстрок текста (начиная с подстроки длины 2 и заканчивая всем текстом). П(T[:1])=0, разумеется.

Улучшение 1. Если для некоторого подслова длины k П(T[:k])==m (совпадают символы T[0]…T[m-1] и T[k-m]…T[k-1]), то П(T[:k+1]) может быть либо на 1 больше (потому что T[m]==T[k]), либо меньше:

1. [[a]]bcdabcfa = 0

2. [a][b]cdabcfa = 0
3. [a]b[c]dabcfa = 0
4. [a]bc[d]abcfa = 0
5. [a]bcd[a]bcfa = 1
6. [ab]cd[ab]cfa = 2
7. [abc]d[abc]fa = 3
8. [abcd][abcf]a = 0 → [abc]da[bcf]a = 0 → [ab]cdeabc[df]a = 0 → [a]bcdeabcd[f]a = 0
9. [a]bcdabcf[a] = 1

П. 7 наводит на мысль, о возможной квадратичности и этого алгоритма в каком-то изощрённом худшем случае.

Улучшение 2. Рассмотрим более общий пример. Предположим, при подсчёте вектора П-функций образуется следующее

При проверке последнего элемента T[5]!=T[11]. Хвост и голова длиной 6 не совпадают, следовательно, если и совпадают, то хвост и голова длины <= 5 . А решение этой задачи у нас уже есть — это П(T[:5]):

То есть 2. Попробуем увеличить эти хвост и голову — получилось, ответ 3:

Остаётся только заметить, что если и этот хвост не подошёл, операцию надо повторить циклически (взять предыдущее решение, увеличить, проверить и т. д.). Существует доказательство линейности получившегося алгоритма.

def PFun(text):
    pi = [0]
    for i in range(1,len(text)):
        j = pi[-1]
        while j and text[i] != text[j]:
            j = pi[j-1]
        if text[i] == text[j]:
            j+=1
        pi.append(j)
    return pi

Поиск шаблона s в тексте t за линейное время с помощью П-функции:

• Составим строку a=s+"#"+t, где "#" — символ, не встречающийся в шаблоне
• Вычислим вектор П-функций

• Если в каком-то месте П-функция равна длине s — это и есть вхождение шаблона в текст

• Ложных срабатываний не будет, потому что "#" не встречается в шаблоне

def PFind(patt, text):
    w = len(patt)
    p = PFun(patt+"\0"+text)[w+1:]
    if w in p:
        return p.index(w)-w+1
    return -1