题解 | 烘焙店的配方检查

def KMP(haystack, needle):
    def build_next(s):
        nxt = [0] * (len(s)+1) 
        j = 0
        for i in range(1, len(s)):
            while j>0 and s[i]==s[j]:
                j = nxt[j-1]
            if s[i]==s[j]:
                j+=1
            nxt[i] = j
        return nxt
    nxt = build_next(needle)
    j = 0
    for i in range(len(haystack)):
        while j>0 and haystack[i]!=needle[j]:
            j = nxt[j-1]
        if haystack[i]==needle[j]:
            j+=1
        if j==len(needle):
            return i-len(needle)+1
    return -1


def main():
    pass
    _input = input().split(' ')
    T = _input[0]
    data = {}
    for string in _input[1:]:
        if KMP(T, string)==0:
            if string in data:
                data[string] += 1
            else:
                data[string] = 1
    if not data:
        print('null')
    else:
        new_data = []
        for key in data.keys():
            new_data.append([key, data[key], len(key)])            

        new_data.sort(key=lambda x: -x[2])
        for ele in new_data:
            print(f'{ele[0]} {ele[1]}')


if __name__ == "__main__":
    main()