دوال السابقة ومطابقات النص المتداخلة

def prefix_function(pattern):
    pi = [0] * len(pattern)
    for i in range(1, len(pattern)):
        j = pi[i - 1]
        while j and pattern[i] != pattern[j]:
            j = pi[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        pi[i] = j
    return pi

print(prefix_function("ababaca"))
print(prefix_function(""))

[0, 0, 1, 2, 3, 0, 1]
[]

عند a الأخيرة يصح حد طوله 1. وعند c تفشل جميع مرشحات الحدود السابقة المكونة من a وb، فيصبح طول الحد 0.

def prefix_function(pattern):
    pi = [0] * len(pattern)
    for i in range(1, len(pattern)):
        j = pi[i - 1]
        while j and pattern[i] != pattern[j]:
            j = pi[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        pi[i] = j
    return pi

def find_all(text, pattern):
    if not pattern:
        return list(range(len(text) + 1))
    pi = prefix_function(pattern)
    matches, j = [], 0
    for i, char in enumerate(text):
        while j and char != pattern[j]:
            j = pi[j - 1]
        if char == pattern[j]:
            j += 1
        if j == len(pattern):
            matches.append(i - len(pattern) + 1)
            j = pi[j - 1]
    return matches

print(find_all("aaaa", "aa"))
print(find_all("باباب", "باب"))
print(find_all("ab", ""))

[0, 1, 2]
[0, 2]
[0, 1, 2]

تستخدم العينة العربية نقاط ترميز دقيقة بلا تشكيل، وتشمل مطابقات متداخلة. ويسرد ناتج النمط الفارغ الحدود، وليس المحارف.