[NC14517]回文串

链接：登录—专业IT笔试面试备考平台_牛客网 来源：牛客网

题目描述

既然大家都知道回文串是怎么回事了，那我们就长话短说，现在有一个字符串，长度小于1200，我想知道最长的回文子串长度是多少。

输入描述:

多组输入，输入字符串只包含小写字母。

输出描述:

每组输出一个数字，表示最长的回文子串。

示例1

输入

aqppqole
ebcml

输出

4 1

代码展示

#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	while(cin>>s){
		int size=s.size();
		int left=0,right=0,maxlen=0,len=1;
		for(int i=0;i<size;i++){
			left=i-1;
			right=i+1;
			// 左边
			while(left>=0&&s[left]==s[i]){
				len++;
				left--;
			} 
			// 右边
			while(right<=size&&s[right]==s[i]){
				len++;
				right++;
			} 
			// 左右
			while(left>=0&&right<=size&&s[left]==s[right]){
				len+=2;
				left--;
				right++;
			} 
			if(len>maxlen){
				maxlen=len;
			}
			len=1;
		}
		cout<<maxlen<<endl;
	}	
}

逻辑详解

1.变量初始化：

• size：存储输入字符串 s 的长度。
• left 和 right：用于标记当前检查的回文子串的左右边界。
• maxlen：记录找到的最长回文子串的长度，初始值为0。
• len：记录当前检查的回文子串的长度，初始值为1。

2.外层循环：

• 遍历字符串 s 的每个字符，使用索引 i。

3.左边检查：

• 从当前字符 s[i] 的左边开始，left 指向 i-1。
• 只要 left 大于等于0且 s[left] 等于 s[i]，就增加 len 并向左移动 left。

4.右边检查：

• 从当前字符 s[i] 的右边开始，right 指向 i+1。
• 只要 right 小于等于 size 且 s[right] 等于 s[i]，就增加 len 并向右移动 right。

5.左右同时检查：

• 这一步是针对以当前字符为中心的回文子串进行检查。
• 只要 left 大于等于0且 right 小于等于 size 且 s[left] 等于 s[right]，就增加 len 并同时向左和向右移动 left 和 right。

6.更新最长回文长度：

• 如果当前检查的回文子串长度 len 大于 maxlen，则更新 maxlen。

7.重置 len：

• 每次检查完一个字符后，重置 len 为1，为下一个字符的检查做准备。

8.输出结果：

• 输出找到的最长回文子串的长度。