Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit6ce18d5

Browse files
manacher
添加manacher算法
1 parent3f1006e commit6ce18d5

File tree

2 files changed

+74
-74
lines changed

2 files changed

+74
-74
lines changed

‎.idea/workspace.xml

Lines changed: 40 additions & 74 deletions
Some generated files are not rendered by default. Learn more aboutcustomizing how changed files appear on GitHub.

‎AwesomeAlgorithms/manacher算法.py

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
# -*- coding:UTF-8 -*-
2+
'''
3+
神之算法-Manacher算法
4+
求最长回文子串
5+
'''
6+
7+
8+
defmanacher(s):
9+
ifs==Noneorlen(s)==0:
10+
return
11+
# 预处理字符串, 把字符串中间和首尾都添加#号, 时的字符串长度变为奇数
12+
# 预处理后的字符串每个位置对应的最长回文串的半径 减去1 等于原始字符串该处对应的最长回文串的长度
13+
s="#"+"#".join(s)+"#"
14+
curLongest= [0]*len(s)# 使用curLongest存储每个位置最长回文串半径
15+
maxRight,mid=0,0# maxRight, mid分别存储之前步骤中所有回文子串所能到达的s最右端坐标以及种鸽回文串的对称轴位置
16+
maxLen=0# maxLen 记录当前的最长回文串的长度
17+
foriinrange(len(s)):
18+
ifi<maxRight:
19+
# i处于maxRight左边有两种情况
20+
# 1. 当前位置i和对称轴pos相对应的位置j在前面操作中拥有的最大回文串半径没有达到maxRight关于pos的对称位置, 此时curLongest[i]从curLongest[2 * mid - i]开始扩张
21+
# 2. 当前位置i和对称轴pos相对应的位置j在前面操作中拥有的最大回文串半径能够达到maxRight关于pos的对称位置, 此时curLongest[i]从maxRight-i的长度开始扩张
22+
curLongest[i]=min(curLongest[2*mid-i],maxRight-i)
23+
else:
24+
# i处于maxRight的位置或者maxRight右边的位置时
25+
curLongest[i]=1
26+
whilei-curLongest[i]>=0andcurLongest[i]+i<len(s)ands[i-curLongest[i]]==s[i+curLongest[i]]:
27+
curLongest[i]+=1
28+
# 如果当前i所对应的回文串最右边长度大于之前maxRight, 更新maxRight和对称轴的位置
29+
ifcurLongest[i]+i-1>maxRight:
30+
maxRight=curLongest[i]+i-1
31+
mid=i
32+
maxLen=max(maxLen,curLongest[i])
33+
returnmaxLen-1
34+
print(manacher('saas'))

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp