recipe-578161.py 文件源码

def transition_function(P):
    """
    The main principle on building the transition function is to think about
    the fact that every time we scan a new character from the input sequence
    the suffix should match with the prefix of the pattern. If that is not
    possible for every length of the suffix, the next state need to be the
    initial, otherwise the length of the suffix that matches properly will be
    exactly the next state.
    """
    alphabet = st.ascii_letters+st.punctuation+st.digits+st.whitespace
    m = len(P)
    trans = [{c:0 for c in alphabet} for i in range(m)]
    for s in range(m):
        for c in alphabet:
            k = min(m, s+1)
            while (P[:s]+c)[-k:] != P[:k]:
                k-=1

            trans[s][c]=k

    return trans