(manacher 1.1)hdu 3068回文(使用manacher判断回文简单题)

小鱼儿 2022-03-01 06:06 187阅读 0赞

# 最长回文 #

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

输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S  
两组case之间由空行隔开(该空行不用处理)  
字符串长度len <= 110000

**Output**

每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.

**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 <vector>
>     #include <iostream>
>     #include <string>
>     #include <cstdio>
>     
>     
>     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<int> 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<int> 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;
>     
>         }
>     }

[2009 Multi-University Training Contest 16 - Host by NIT]: http://acm.hdu.edu.cn/search.php?field=problem&key=2009+Multi-University+Training+Contest+16+-+Host+by+NIT&source=1&searchmode=source
[3336]: http://acm.hdu.edu.cn/showproblem.php?pid=3336
[3065]: http://acm.hdu.edu.cn/showproblem.php?pid=3065
[3067]: http://acm.hdu.edu.cn/showproblem.php?pid=3067
[3063]: http://acm.hdu.edu.cn/showproblem.php?pid=3063
[3064]: http://acm.hdu.edu.cn/showproblem.php?pid=3064