2017年上海金马五校程序设计竞赛：Find Palindrome

水深无声 2022-06-14 00:53 133阅读 0赞

## Description ##

Given a string S, which consists of lowercase characters, you need to find the longest palindromic sub-string.  
  
A sub-string of a string S  is another string S'  that occurs "in" S. For example, "abst" is a sub-string of "abaabsta". A palindrome is a sequence of characters which reads the same backward as forward.

## Input ##

There are several test cases.  
Each test case consists of one line with a single string S (1 ≤ |S | ≤ 50).

## Output ##

For each test case, output the length of the longest palindromic sub-string.

## Sample Input ##

sasadasa
    bxabx
    zhuyuan

## Sample Output ##

7
    1
    3

#include <bits/stdc++.h>
    using namespace std;
    int xd(char a[],int w,int i,int j)
    {
        int u=0;
        while(j>i)//j即倒数字符要一直大于i即正数字符
        {
            if(a[i]==a[j]&&a[i+1]==a[j-1])//如果相等并且下一对也相等，则数目加2；否则不匹配数目归零
            {
                u=u+2;
            }
            else
            {
                u=0;
            }
            i=i+1;
            j=j-1;
        }
        if(i==j)//如果是回文串是奇数则数目加一，如果不是，则不加
        {
            u=u+1;
        }
        return u;
    }
    int main()
    {
        int n,i,j,q,w,u,v;
        char a[51];
        while(gets(a))
        {
            i=0;
            u=0;
            w=strlen(a);
            j=w-1;
            for(i=0;i<w;i++)//循环比较开始字符和倒数字符
                for(j=w-1;j>=i;j--)
            {
                if(a[i]==a[j])//如果相等则进去函数
                {
                    v=xd(a,w,i,j);
                    if(v>u)
                        u=v;
                }
            }
            cout<<u<<endl;
        }
        return 0;
    }