团体程序设计天梯赛-练习集 L2-008 最长对称子串 (25分) 马拉车算法

阳光穿透心脏的1/2处 2023-10-11 14:53 16阅读 0赞

### L2-008 最长对称子串 (25分) ###

对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出11。

**输入格式：**  
输入在一行中给出长度不超过1000的非空字符串。

**输出格式：**  
在一行中输出最长对称子串的长度。

**输入样例：**

Is PAT&TAP symmetric?

**输出样例：**

> 本题思路：参考马拉车算法，马拉车算法是专门求最长回文串的算法！  
> [参考博客：https://www.cnblogs.com/8023spz/p/10620045.html][https_www.cnblogs.com_8023spz_p_10620045.html]  
> [思路参考：https://www.bilibili.com/video/BV187411B79Q?from=search&seid=6240992414088209386][https_www.bilibili.com_video_BV187411B79Q_from_search_seid_6240992414088209386]

#include<iostream>
    #include<cstring>
    #include<algorithm>
    
    const int N = 1005;
    using namespace std;
    char s[N], t[2*N+5] = {
        '$','#'};
    int p[2*N+5];
    
    int Manacher(char *str){
        
    	int len = strlen(str);
    	for(int i = 1; i <= len; i ++){
        
    		t[i*2] = str[i-1];
    		t[i*2+1] = '#';
    	}
    	t[len*2+2] = 0;
    	
    	int mi, rpoint, mr;//mi中心， rpoint右边界， mr最长子串长度+1
    	mi = rpoint = mr = 0;
    	for(int i = 1; t[i]!=0; i ++){
        
    		p[i] = i<rpoint?min(rpoint-i, p[mi*2-i]):1;
    		while(t[i+p[i]]==t[i-p[i]])
    			p[i]++;
    			
    			
    		if(i+p[i]>rpoint){
        
    			mi = i;
    			rpoint = i + p[i];
    		}
    		if(mr<p[i]){
        
    			mr = p[i];
    		}
    	}
    	return mr-1;
    	
    }
    
    
    int main(){
        
    	int i = 0;
    	while((s[i] = getchar())!='\n'){
        
    		i++;
    	}
    	s[i] = 0;
    	cout << Manacher(s) << endl;
    	return 0;
    }

[https_www.cnblogs.com_8023spz_p_10620045.html]: https://www.cnblogs.com/8023spz/p/10620045.html
[https_www.bilibili.com_video_BV187411B79Q_from_search_seid_6240992414088209386]: https://www.bilibili.com/video/BV187411B79Q?from=search&seid=6240992414088209386