精华内容
下载资源
问答
  • 马拉车算法

    2020-03-18 11:16:04
    马拉车算法是一种计算最长回文子串的算法,以其优秀的线性复杂度闻名于世,相较于O(n2)O(n^2)O(n2)的dpdpdp算法和会被特殊数据卡到O(n2)O(n^2)O(n2)的暴力算法,马拉车算法无疑是求解最长回文子串的最优选择。...

    马拉车算法是一种计算最长回文子串的算法,以其优秀的线性复杂度闻名于世,相较于 O ( n 2 ) O(n^2) O(n2) d p dp dp算法和会被特殊数据卡到 O ( n 2 ) O(n^2) O(n2)的暴力算法,马拉车算法无疑是求解最长回文子串的最优选择。
    最长回文子串分为偶数串和奇数串,为了避免这些问题,马拉车算法将每个字符与字符间插入一个特殊字符,在两头插入不同的字符,以免越界。
    马拉车算法定义: r r r为当前已知的对称的最右边的点, m i d mid mid r r r的对称轴, f i f_i fi为以 i i i为对称轴的最长回文子串的回文半径
    则我们遇到一个 i i i,分两种情况讨论
    m i d ≤ i ≤ r mid \leq i \leq r midir,则 f i f_i fi可能为他的对称点,即 f m i d ∗ 2 − i f_{mid*2-i} fmid2i,但如果 i + f m i d ∗ 2 − i i+f_{mid*2-i} i+fmid2i大于了 r r r,则就不能保证它的正确性,而能保证正确性的区域在哪儿呢?只有 r r r以内,所以要和 r − i + 1 r-i+1 ri+1取一个 m i n min min,然而我们不能保证它的最长回文子串一定是这个范围,所以我们要暴力拓展一下,直到不能拓展为止。
    r < i r<i r<i,那么暴力拓展即可。
    而做完这一切后,看看 r r r m i d mid mid有没有要更新的。
    而我们统计答案时一定要减掉插入的字符,我们发现,统计出来的回文半径一定是一个奇数,则结尾是一个 # \# #,将对面的对过来,得到答案为 f i − 1 f_i-1 fi1最终答案即为 m i n ( f i ) − 1 min(f_i)-1 min(fi)1
    那么马拉车算法的时间复杂度是怎么证明为线性呢?
    若是 m i d ≤ i ≤ r mid \leq i \leq r midir且取值为 f m i d ∗ 2 − i f_{mid*2-i} fmid2i,那么是一定不会拓展的,因为这还在这个回文半径里面,两边肯定是相同的
    而其他两种情况, r r r是一定随着动的。所以复杂度为线性,即 O ( n ) O(n) O(n)
    代码实现:

    #include<cstdio>
    #include<cstring>
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    using namespace std;
    int n,m,k,f[2000039],mr,mid,ans;
    char s[2000039],x;
    int main(){
    	register int i;
    	s[++n]='%';
    	s[++n]='#';
    	x=getchar();
    	while(x>='a'&&x<='z') s[++n]=x,s[++n]='#',x=getchar();
    	s[++n]='&';
    	mr=mid=1;
    	for(i=2;i<n;i++){
    		if(i<mr) f[i]=min(f[mid*2-i],mr-i+1);
    		while(s[i+f[i]]==s[i-f[i]]) f[i]++;
    		if(f[i]+mid>mr) mr=f[i]+i-1,mid=i;
    		ans=max(ans,f[i]-1);
    	}
    	printf("%d\n",ans);
    }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,825
精华内容 1,130
关键字:

马拉车算法