(manacher 1.1) hdu 3068 회 문 (manacher 로 회 문 을 판단 하 는 간단 한 문제)

최 장 답문
Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 33140    Accepted Submission(s): 12132  
Problem Description
소문 자 영문 문자 a, b, c... y, z 로 만 구 성 된 문자열 S 를 보 여 줍 니 다. S 에서 가장 긴 답장 문자열 의 길 이 를 구 합 니 다. 답장 은 정반 독 과 같은 문자열 입 니 다. 예 를 들 어 aba, abba 등 입 니 다.
 
 
Input
120 그룹 을 초과 하지 않 고 여러 그룹의 case 를 입력 하 십시오. 각 그룹 은 소문 자 영문 문자 a, b, c... y, z 로 구 성 된 문자열 S 두 그룹의 case 사 이 를 빈 줄 로 구분 합 니 다 (이 빈 줄 은 처리 하지 않 음) 문자열 길이 len < = 110000
 
 
Output
각 줄 의 정수 x 는 하나의 케이스 에 대응 하여 이 케이스 의 문자열 에 포 함 된 가장 긴 답장 길 이 를 표시 합 니 다.
 
 
Sample Input

aaaa abab
 
 
Sample Output

4 3
 
 
Source
2009 Multi-University Training Contest 16 - Host by NIT
 
 
Recommend
lcy   |   We have carefully selected several similar problems for you:  3336 3065 3067 3063 3064 
 

#include 
#include 
#include 
#include 


using namespace std;

const int MAXN = 100005;


//string Manacher(string s) {
//    // Insert '#'
//    string t = "$#";
//    for (int i = 0; i < s.size(); ++i) {
//        t += s[i];
//        t += "#";
//    }
//
//    // Process t
//    vector p(t.size(), 0);
//
//
//    int mx = 0, id = 0, resLen = 0, resCenter = 0;
//    for (int i = 1; i < t.size(); ++i) {
//
//        //找到回文串的长度
//        p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
//
//        /*
//         * 尝试拓宽边界
//         */
//        while (t[i + p[i]] == t[i - p[i]]) {
//            ++p[i];
//        }
//
//        /*
//         * 更新回文串的边界
//         */
//        if (mx < i + p[i]) {
//            //更新回文串右边的边界
//            mx = i + p[i];
//            //更新回文串的中心
//            id = i;
//        }
//
//        //更新回文串的中心数据
//        if (resLen < p[i]) {
//
//            //回文串的半径(就是处理后的回文串)
//            resLen = p[i];
//            //回文串的中心
//            resCenter = i;
//
//        }
//    }
//
//    /*
//     * s是原来的文本串.
//     *
//     * resLen:处理后的回文串的半径,但是是处理前的回文串的直径
//     * resCenter:处理后的回文串的中心
//     *
//     * resCenter - resLen:计算回文串的起点
//     * resLen - 1:需要
//     */
//    return s.substr((resCenter - resLen) / 2, resLen - 1);
//}


string manacher(string s) {


    int mx = 0;
    int id = 0;
    int resCenter = 0;
    int resLen = 0;


    string t = "$#";
    for (int i = 0; i < s.length(); ++i) {
        t += s[i];
        t += "#";
    }


    vector p(t.length(), 0);
    for (int i = 0; i < t.length(); ++i) {
        p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;


        while (t[i + p[i]] == t[i - p[i]]) {
            p[i] += 1;
        }


        if (mx < i + p[i]) {
            mx = i + p[i];
            id = i;
        }

        if (resLen < p[i]) {
            resLen = p[i];
            resCenter = i;
        }

    }


    return s.substr((resCenter - resLen) / 2, resLen - 1);
}


int main() {
//    string s1 = "12212";
//    cout << Manacher(s1) << endl;
//    string s2 = "122122";
//    cout << Manacher(s2) << endl;
//    string s = "waabwswfd";
//    cout << Manacher(s) << endl;
//
//
//    cout << "----------" << endl;
//
//    cout << manacher(s1) << endl;
//    string s22 = "122122";
//    cout << manacher(s22) << endl;
//    string s33 = "waabwswfd";
//    cout << manacher(s33) << endl;

//      string tmp = "";

    char tmp[MAXN];
    while (scanf("%s", tmp) != EOF) {
        string result = manacher(tmp);

        cout << result.length() << endl;

    }
}