这里有一个向量化的解决方案。
它创建对输出数组的对角线视图，使我们能够在对角线方向上进行累积。
逐步说明：
- 在对角线视图中评估 s[i] == s[j]。
- 仅保留那些通过从右上到左下方向的一系列True与主对角线或第一子对角线相连的元素。
- 用2替换所有True，除了主对角线，主对角线用1代替；在从左下到右上方向上进行累计求和。
- 最后，在从下到上和从左到右的方向上进行累积最大值。
由于不是完全明显，这个方法做的事情与循环代码相同。我已经使用函数stresstest在许多示例中进行了测试，看起来是正确的。而且对于中等大小的字符串（1-100个字符），速度大约快7倍。
import numpy as np
def loopy(s):
n = len(s)
opt = np.zeros(shape=(n, n), dtype=int)
for j in range(0, n):
for i in range(j, -1, -1):
if j - i == 0:
opt[i, j] = 1
elif j - i == 1:
opt[i, j] = 2 if s[i] == s[j] else 1
elif s[i] == s[j] and opt[i + 1, j - 1] == (j - 1) - (i + 1) + 1:
opt[i, j] = 2 + opt[i + 1, j - 1]
else:
opt[i, j] = max(opt[i + 1, j], opt[i, j - 1], opt[i + 1, j - 1])
return opt
def vect(s):
n = len(s)
h = (n+1) // 2
s = np.array([s, s]).view('U1').ravel()
opt = np.zeros((n+2*h-1, n+2*h-1), int)
y, x = opt.strides
hh = np.lib.stride_tricks.as_strided(opt[h-1:, h-1:], (2, h, n), (x, x-y, x+y))
p, o, c = np.ogrid[:2, :h, :n]
hh[...] = 2 * np.logical_and.accumulate(s[c+o+p] == s[c-o], axis=1)
np.einsum('ii->i', opt)[...] = 1
hh[...] = hh.cumsum(axis=1)
opt = np.maximum.accumulate(opt[-h-1:None if h == 1 else h-2:-1, h-1:-h], axis=0)[::-1]
return np.maximum.accumulate(opt, axis=1)
def stresstest(n=100):
from string import ascii_lowercase
import random
from timeit import timeit
Tv, Tl = 0, 0
for i in range(n):
s = ''.join(random.choices(ascii_lowercase[:random.randint(2, 26)], k=random.randint(1, 100)))
print(s, end=' ')
assert np.all(vect(s) == loopy(s))
Tv += timeit(lambda: vect(s), number=10)
Tl += timeit(lambda: loopy(s), number=10)
print()
print(f"total time loopy {Tl}, vect {Tv}")
演示：
>>> stresstest(20)
caccbbdbcfbfdcacebbecffacabeddcfdededeeafaebeaeedaaedaabebfacbdd fckjhrmupcqmihlohjog dffffgalbdbhkjigladhgdjaaagelddehahbbhejkibdgjhlkbcihiejdgidljfalfhlaglcgcih eacdebdcfcdcccaacfccefbccbced agglljlhfj mvwlkedblhvwbsmvtbjpqhgbaolnceqpgkhfivtbkwgbvujskkoklgforocj jljiqlidcdolcpmbfdqbdpjjjhbklcqmnmkfckkch ohsxiviwanuafkjocpexjmdiwlcmtcbagksodasdriieikvxphksedajwrbpee mcwdxsoghnuvxglhxcxxrezcdkahpijgujqqrqaideyhepfmrgxndhyifg omhppjaenjprnd roubpjfjbiafulerejpdniniuljqpouimsfukudndgtjggtbcjbchhfcdhrgf krutrwnttvqdemuwqwidvntpvptjqmekjctvbbetrvehsgxqfsjhoivdvwonvjd adiccabdbifigeigdfaieecceciaghadiaigibehdaichfibeaggcgdciahfegefigghgebhddciaei llobdegpmebejvotsr rtnsevatjvuowmquaulfmgiwsophuvlablslbwrpnhtekmpphsenarhrptgbjvlseeqstewjgfhopqwgmcbcihljeguv gcjlfihmfjbkdmimjknamfbahiccbhnceiahbnhghnlleimmieglgbfjbnmemdgddndhinncegnmgmfmgahhhjkg nhbnfhp cyjcygpaaeotcpwfhnumcfveq snyefmeuyjhcglyluezrx hcjhejhdaejchedbce
total time loopy 0.2523909523151815, vect 0.03500175685621798
