境界 (border)

基本概念

文字列 \(w\) に対し, \(w\) の接頭辞でもあり接尾辞でもある文字列を \(w\)境界 (border) という. \(w\) 自身と,空語 \(\varepsilon\) は常に \(w\) の境界である.

\(w\) の自明でない(つまり \(w\) 自身ではない)最長の境界を \(Border(w)\) と表す.

注釈

例えば, \(Border(abaababa) = aba\) である.

境界は, 周期 (period) と表裏の関係にある.

アルゴリズム

入力として与えられた文字列の境界配列 (border array)を求める問題

文字列 \(w\) に対し, \(border[i] = Border(w[:i])\) で定義される配列 \(border\) を考える.

注釈

文字列 abaababa に対する境界配列

i 0 1 2 3 4 5 6 7 8
文字   a b a a b a b a
border -1 0 0 1 1 2 3 2 3

この境界配列は, Knuth-Morris-Pratt法 の肝になっている.

def border():
    inp = raw_input()
    bordArray = [-1]
    bord = 0

    for i in range(len(inp)):
        pref = inp[:i+1]
        for j in range(len(pref)):
            if pref[-len(pref[:j+1]):] == pref[:j+1] and len(pref[:j+1]) != len(pref):
                    bord = max(bord,len(pref[:j+1]))
                    print("bord =",bord)
        bordArray.append(bord)
        bord = 0
        
    return bordArray
def compute_border1():
    pat = raw_input()
    
    """-1で初期化"""
    m = len(pat)
    Bord = [-1]*(m+1)
    
    pat = " " + pat
    i,j = 1,0

    while i < m + 1:
        if Bord[i+j] == -1:
            Bord[i+j] = j;
        while i + j < m and pat[j+1] == pat[i+j+1]:
            j += 1
            if Bord[i+j] == -1:
                Bord[i+j] = j;
        i = i + j - Bord[j]
        j = max(0,Bord[j])
    return Bord
def compute_border2():
    pat = raw_input()

    t = -1
    Bord = [-1]
    #"""-1で初期化"""
    #for i in range(len(pat)):
    #    Bord.append(-1)
    """パターンの長さm"""
    m = len(pat)
    """patを[1...m]に"""
    pat = " " + pat
    
    for j in range(m):
        while t >= 0 and pat[t+1] != pat[j+1]:
            t = Bord[t];
        t = t + 1
        #Bord[j+1] = t       
        Bord.append(t)
    return Bord


参考文献