 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
接下面的算法，另一种解法。。（S与转置串的最长公共子序列）可以换一种思路来理解这道题，S=（s1,s2,s3,...,sn）来表示原串。
要求把S 变为回文，需要多少步？
其实，它的反问题就是S的子串中，构成回文的最大子串是什么？？
比如S=(a,b,c,d,c,e),它子串总最大回文为S1=(c,d,c)，那么要把整体S变为回文，需要步数为len(S)-len(S1)=6-3=3。
所以，要找到构成回文的最大子串。。
只需要把S转置成^S，求 S、^S的 最长公共子序列。。
问题答案为 len(S)-LCS(S,^S)，其中^S为S的转置串，LCS(S,^S)为最长公共子序列的长度。。
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
