Avalonia UI的演进逻辑与Qt生态深度对比
堪粤尚冀最长相等真前后缀
最长相等前后缀也被称为 Border ，KMP算法就利用了其性质来进行匹配优化。
前缀：从字符串第一个字符开始的子串。
后缀：以字符串最后一个字符结束的子串。
真：长度严格小于原字符串长度。
求法（
?
(
?
2
)
O(n
2
) ）：
def border(s):
n = len(s)
L = 0
for i in range(1, n): # 长度为 i 上限为 n-1 确保为真前后缀
if s[:i] == s[n-i:n]:
L = i
return L
还有更加高效的算法，可以优化到
?
(
?
)
O(n) 。正是这个优化产生了 KMP 算法。
前缀函数
在 KMP 中的前缀函数的到数组
?
π ，其中
?
[
?
]
π[i] 表示字符串的前缀
?
[
0
…
?
]
t[0…i] 中，最长的相等真前后缀的长度。
如果使用暴力枚举每个子串进行一次 border 函数的话时间复杂度是
?
(
?
3
)
O(n
3
)
b = []
for i in range(len(s)):
b.append(border(s[:i + 1]))
通过递推可以在
?
(
?
)
O(n) 时间内求出前缀数组
?
π
假设我们正在计算
?
[
?
]
π[i] ，并且已知
?
[
?
?
1
]
=
?
π[i?1]=j 。
这意味着
?
[
0
…
?
?
1
]
t[0…j?1] 是
?
[
0
…
?
?
1
]
t[0…i?1] 的最长相等前后缀。
情况A：如果
?
[
?
]
=
=
?
[
?
]
t[i]==t[j] ，那么
?
[
?
]
=
?
+
1
π[i]=j+1 。
情况B：如果
?
[
?
]
≠
?
[
?
]
t[i]
=t[j] ，我们需要一个更短的相等前后缀。于是我们可以让
?
=
?
[
?
?
1
]
j=π[j?1] ，然后重复
?
[
?
]
t[i] 和
?
[
?
]
t[j] 的比较过程，直到匹配或
?
j 降为
0
0 。
具体代码为
def get_pi(s):
n = len(s)
pi = [0] * n
for i in range(1, n):
j = pi[i - 1] # 取前一个的位置的pi
while j > 0 and s[i] != s[j]: # 情况B
j = pi[j - 1]
if s[i] == s[j]: # 情况A
j += 1
pi[i] = j
return pi
应用
模式串匹配
已知模式串
?
t 和匹配串
?
s ，在预处理完模式串的
?
π 数组后可以通过双指针匹配。
指针
?
i ：始终在
?
s 上向右移动，不回退。
指针
?
j ：在
?
t 上移动，如果匹配 j++ 如果失配
?
j 根据
?
π 数组向左跳，跳到一个可以让前面部分继续匹配的位置。
这个根据
?
π 数组向左跳的过程可以理解成下面这句有名名的话：
一个人能走的多远不在于他在顺境时能走的多快，而在于他在逆境时多久能找到曾经的自己。
m, n = len(t), len(s)
pi = get_pi(t)
j = 0 # 模式串指针
for i in range(n): # 文本串指针永不回退
while j > 0 and s[i] != t[j]:
j = pi[j - 1]
if s[i] == t[j]:
j += 1
if j == m: # 匹配成功
# 位置为 i - j + 1 0-based
j = pi[j - 1] # 继续匹配可能重叠的下一处
求字符串周期
先利用预处理的
?
π 数组求出所有的 Border ，再根据这些 Border 就可以构造出所有的周期串了。
求字符串所有周期
由于
?
π 数组记录了最长 Border ，而次长的 Border 可能通过
?
[
?
[
?
?
1
]
?
1
]
π[π[n?1]?1] 递归求得，因此我们可以不断回跳，求出所有的 Border 后，周期就是 n - Border。
n = len(s)
pi = get_pi(s)
b = []
k = pi[n - 1]
while k:
b.append(n - k)
k = pi[k - 1]
b.append(n)
print(*b)
不要忘记了
?
s 自身也是周期，然后每个周期串就是 s[:b[i]] 。
完全循环
在
?
[
?
?
1
]
>
0
π[n?1]>0 基础上，当它的最小正周期
?
?
?
[
?
?
1
]
n?π[n?1] 可以被总长度
?
n 整除时，存在完全循环。
n = len(s)
pi = get_pi(s)
k = n - pi[n - 1]
print("YES" if pi[n - 1] > 0 and n % k == 0 else "NO")