-problem: 给你一个长度不大于50000的串, 问它最少可以由多少个回文子串拼接而成, 子串可以重叠. solution: 原串拼接反转串后构造后缀数组, RMQ预处理height数组, 再预处理出以i为首的最长回文子串长度, 然后贪心. ----link: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3671 ----code: https://docs.google.com/document/pub?id=1V2_nl-QEyeBW8PODGwwdVXTABTTmoineOnBo2H2gT_Q
把原串reverse一下接在原串后, 用’$'分隔, 建立后缀数组.
预处理出f[i], 表示以i为首的最长的回文串的长度. f[i]的构造方法后面再说.
再从f[i]构造g[i], g[i]=max{j+f[j]|j∈[0,i]}
然后令i=0, 递推i=g[i], 直到i=n, 递推次数即答案.
最后的递推不难想到, 就是一个贪心. 直观上理解就是一个游标开始在最左边, 从游标位置开始找最大的回文子串游标移动到子串尾部, 然后游标后退一点, 从游标位置继续找回文子串, 使得找到的回文子串能延伸得最远.
最难的地方是f[i]的构造, 这个我想了很久.
因为以i为首的一个子串的长度与它是否是回文子串的函数关系不具有单调性, 所以不能二分答案.
要使f的构造复杂度要在O(n^2)以下, 就不能将每个f[i]孤立来看, 必须利用各个f[i]之间的关系.
关键在于f[i]的这个性质: f[i-1]≤f[i]+2.
用反证法可以轻易证明.
所以令f[n-1]=1, n为原串长度. 然后用f[i]推出f[i-1], 有两种情况:
1. i+f[i]<n and s[i-1]=s[i+f[i]], 则f[i-1]=f[i]+2 2. else, 从大到小枚举f[i-1]的长度, 用后缀数组+RMQ判断是否是回文.
其中s表示原串.
构造f的复杂度感觉是O(n)的, 但是不知道怎么证明…
@update 2010-10-12:
我SB了, f[i]可以通过求以j为中点的最长回文字串得到.
Post a Comment