python数据结构关于改良的KMP算法求模式串t在目标串s中匹配成功的次数及其位置

设计一个算法exp4.cpp ，包含以下子算法，实现从键盘输入目标串s和模式串t，利用改良的KMP算法求模式串t在目标串s中匹配成功的次数及其位置：
（1）CreatStr(s,cstr)：根据字符串常量创建串s；
（2）Getnextval(t,nextval)：求模式串t 的nextval[]的值；
（3）KMPvalIndex(s,t)：利用改良后的KMP算法求模式串t 在目标串s中的匹配成功的次数及其位置，建议采用顺序表L保存每次匹配成功的位置并返回该顺序表；鼓励大家采用更好的方法解决这个问题；若匹配成功，则输出其成功次数及其每次的匹配位置；若匹配失败则输出匹配失败；
（4）以表格的形式展现模式串t的nextval[]的值。
j
t.data[j]
nextval[j]

【测试实例】
请输入目标串：Welcome to Xiangtan! Xiangtan is a beautiful city!
请输入模式串：Xiangtan
目标串：s=“Welcome to Xiangtan! Xiangtan is a beautiful city!”
模式串：t=“Xiangtan”
模式串t在目标串s中出现了2次！

大概有张结构图，但不会写主程序

仅供参考，望采纳：

def CreatStr(s, cstr):
    """
    根据字符串常量创建串 s
    """
    s = cstr

def Getnextval(t, nextval):
    """
    求模式串 t 的 nextval[] 的值
    """
    nextval[0] = -1
    i = 0
    j = -1
    while i < len(t) - 1:
        if j == -1 or t[i] == t[j]:
            i += 1
            j += 1
            nextval[i] = j
        else:
            j = nextval[j]

def KMPvalIndex(s, t):
    """
    利用改良后的 KMP 算法求模式串 t 在目标串 s 中的匹配成功的次数及其位置
    若匹配成功，则输出其成功次数及其每次的匹配位置
    若匹配失败则输出匹配失败
    """
    nextval = [0] * len(t)
    Getnextval(t, nextval)
    i = 0
    j = 0
    while i < len(s) and j < len(t):
        if j == -1 or s[i] == t[j]:
            i += 1
            j += 1
        else:
            j = nextval[j]
    if j == len(t):
        return i - j
    else:
        return -1

def main():
    s = input("请输入目标串：")
    t = input("请输入模式串：")
    index = KMPvalIndex(s, t)
    if index == -1:
        print("匹配失败")
    else:
        count = 1
        while index != -1:
            count += 1
            index = KMPvalIndex(s[index+len(t):], t)
        print(f"模式串 t 在目标串 s 中出现了 {count} 次！")

if __name__ == "__main__":
    main()