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

╰+攻爆jí腚メ 2022-06-13 23:47 112阅读 0赞

### Problem E : Find Palindrome ###

From: [DHUOJ, 2017060305][DHUOJ_ 2017060305]

Submit (Out of Contest)

Time Limit: 1 s

--------------------

## 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

这道题就是求最长回文字符字串的长度

我的思路，哈哈哈，就是暴力，直接从第一个开始一个一个挨着判断。但是光是这样可不行，要分两种情况

第一种：以一个单独字母为中心，依次向左向右对称的，如abcba这样的。

第二种：以一对字母为中心，然后依次向左向右对称的，如abccba这样的。

两种情况分别计算，最后求出最长的，很不错，暴力直接就过了呢。^-^

#include <cstdio>
    #include <cmath>
    #include<iostream>
    #include<cstring>
    using namespace std;
    int main()
    {
        char s[61];
        while(cin>>s)
        {
        int i,j,a,max=0,t,min=0,k;
        a=strlen(s);
         for(i=0;i<a;i++)
         {
             t=0;
             for(j=1;;j++)
             {
             if(s[i-j]==s[i+j]&&i-j>=0&&i+j<a)
             {
                 t++;
             }
             else
             {
                 if(t>max)
                    max=t;
                 break;
             }
             }
         }
         for(i=0;i<a;i++)
         {
             t=0;
             k=0;
             for(j=1;;j++)
             {
                 if(s[i-k]==s[i+j]&&i-k>=0&&i+j<a)
                 {
                     t++;
                     k++;
                 }
                 else
                 {
                 if(t>min)
                    min=t;
                 break;
                 }
             }
         }
         max=max*2+1;
         min=min*2;
         if(max>min)
            printf("%d\n",max);
         else
            printf("%d\n",min);
        }
         return 0;
    }

dalao又讲了一种比较高逼格的算法manacher算法，好像是专门用来求最长回文字串的。学的并不是很好。。

[附上一个链接][Link 1]

[DHUOJ_ 2017060305]: http://acm.dhu.edu.cn/dhuoj
[Link 1]: https://segmentfault.com/a/1190000003914228