首页 > 代码库 > Hdu 3068 最长回文字串Manacher算法

Hdu 3068 最长回文字串Manacher算法

2024-07-16 11:04:59   220人阅读

题目链接

最长回文

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7976    Accepted Submission(s): 2735


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
aaaaabab

 

Sample Output
43

 关于Manacher算法的介绍，网上可以找到很多资料。O(N)

Accepted Code:

 1 /************************************************************************* 2     > File Name: hdu_3068.cpp 3     > Author: Stomach_ache 4     > Mail: sudaweitong@gmail.com 5     > Created Time: 2014年08月04日 星期一 18时44分05秒 6     > Propose: hdu3068, poj3974 7  ************************************************************************/ 8 // Manacher O(n) 9 #include <cmath>10 #include <string>11 #include <cstdio>12 #include <fstream>13 #include <cstring>14 #include <iostream>15 #include <algorithm>16 using namespace std;17 18 const int maxn = 100005;19 char s[maxn], str[maxn<<1];20 int p[maxn<<1], n;21 22 void Manacher() {23       n = strlen(s);24     str[0] = ‘$‘;25     str[1] = ‘#‘;26     for (int i = 0; i < n; i++) {27         str[i*2+2] = s[i];28           str[i*2+3] = ‘#‘;29     }30     n = n * 2 + 2;31     str[n] = 0;32 33     int mx = 0;34     int id;35     for (int i = 1; i < n; i++) {36           if (mx > i) p[i] = min(p[2*id-i], mx - i);37         else p[i] = 1;38         for ( ;str[i-p[i]] == str[i+p[i]]; p[i]++);39         if (p[i] + i > mx) {40               mx = p[i] + i;41             id = i;42         }43     }44 }45 46 void solve() {47     Manacher();48     int ans = 0;49     for (int i = 0; i < n; i++) ans = max(ans, p[i]);50     printf("%d\n", ans - 1);51 }52 53 int main(void) {54       while (~scanf("%s", s)) {55           solve();56     }57 58     return 0;59 }

 


联系
我们