首页 > itarticle > 回文串

回文串

admin 11月 13, 2020 0

宇智波鼬

概念：

什么是回文串
“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。

实现：

循环中间节点，逐步向两边遍历
从两边向中间遍历。一次可以遍历两个，算法复杂度为nlogn

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1000+10;
int vis[maxn][maxn];
string str;
int p[maxn][maxn];
int pa(int i,int j){
    if(i>=j)return 1;
    if(str[i]!=str[j])return 0;
    if(vis[i][j])return p[i][j];
    vis[i][j]=1;
    p[i][j]=pa(i+1,j-1);
    return p[i][j];
}
int main()
{

	while(getline(cin,str)){
        memset(vis,0,sizeof vis);
        int ans=0;
        int len=str.length();
        for(int i=0;i<len;i++){
            for(int j=i;j<len;j++){
                if(pa(i,j))ans=max(ans,j-i+1);
            }
        }
        cout<<ans<<endl;
	}
    return 0;
}