程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 1040. Longest Symmetric String (25)最長回文子串-馬拉車(manacher算法)——PAT (Advanced Level) Practise

1040. Longest Symmetric String (25)最長回文子串-馬拉車(manacher算法)——PAT (Advanced Level) Practise

編輯:C++入門知識

1040. Longest Symmetric String (25)最長回文子串-馬拉車(manacher算法)——PAT (Advanced Level) Practise


題目信息

1040. Longest Symmetric String (25)

時間限制400 ms
內存限制65536 kB
代碼長度限制16000 B

Given a string, you are supposed to output the length of the longest symmetric sub-string. For example, given “Is PAT&TAP symmetric?”, the longest symmetric sub-string is “s PAT&TAP s”, hence you must output 11.

Input Specification:

Each input file contains one test case which gives a non-empty string of length no more than 1000.

Output Specification:

For each test case, simply print the maximum length in a line.

Sample Input:
Is PAT&TAP symmetric?
Sample Output:
11

解題思路

manacher算法,不懂的可參照我的另一篇博文:http://blog.csdn.net/xianyun2009/article/details/46767829

AC代碼

#include 
#include 
using namespace std;
char s[2010];
int r[2010];
int ch, p = 0;
int manacher(){
    int cn = 0, mx = 0, re = 0;
    for (int i = 1; i < p; ++i){
        r[i] = (mx > i) ? min(r[cn * 2 - i], mx - i) : 1;
        while (s[i + r[i]] == s[i - r[i]]) ++r[i];
        if (i + r[i] > mx){
            mx = i + r[i];
            cn = i;
        }
        if (r[i] > re) re = r[i];
    }
    return re - 1;
}

int main()
{
    s[p++] = '\1'; //特殊字符
    while ((ch = getchar()) && ch != '\n'){
        s[p++] = '\3';
        s[p++] = ch;
    }
    s[p++] = '\3';
    printf("%d\n", manacher());
    return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved