蓝桥杯算法训练-Tricky and Clever Password-题解（Python代码）

解题思路:
https://blog.csdn.net/eveee1123/article/details/113706481

详情

注意事项:

参考代码:

def KMP(s,p):
    s=' '+s
    p=' '+p
    n=len(s)-1
    m=len(p)-1
    match=[None for i in range(n+1)]
    ne=[0 for i in range(m+10)]
    j=0
    for i in range(2,m+1):
        while(j and p[i]!=p[j+1]): j=ne[j]
        if p[i]==p[j+1]: j+=1
        ne[i]=j
    j=0
    for i in range(1,n+1):
        while(j and s[i]!=p[j+1]): j=ne[j]
        if s[i]==p[j+1]: j+=1
        match[i]=j
    return match
def init(st):
    tmp=[None for i in range((len(st)<i:
            p[i]=min(R-i,p[i_mirror])
        else:
            p[i]=0
        while(st[i+1+p[i]]==st[i-1-p[i]]):
            p[i]+=1
        if i+p[i]>R:
            C=i
            R=i+p[i]
    return p
s=input()
dp=[0 for i in range(len(s)+10)]
tail=[0 for i in range(len(s)+10)]
p=manacher(init(s))
re_s=list(s);re_s.reverse()
re_s=''.join(re_s)
f=KMP(s,re_s)
for i in range(1,len(s)+1):
    if dp[i-1]ans:
        final=[]
        ans=2*pre_suf+p[center]
        if pre_suf: final.append((tail[i-R]-pre_suf+1,pre_suf))
        final.append((i-R+1,p[center]))
        if pre_suf: final.append((len(s)-pre_suf+1,pre_suf))
print(len(final))
for i in final:
    print(i[0],i[1])