首页 > 代码库 > hdu--3068 最长回文串（manachar模板）

hdu--3068 最长回文串（manachar模板）

2024-08-24 13:37:05   220人阅读

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
题意：中文题目不解释
思路：直接套用manachar算法返回结果即为最长回文串的长度
算法模板：
技术分享 
 1 int manachar(int len)
 2 {
 3     int maxn,mx,id;
 4     maxn=mx=id=0;
 5     memset(p,0,sizeof(p));
 6     for(int i=1;i<len;i++)
 7     {
 8         if(mx>i)
 9             p[i]=min(p[id*2-i],mx-i);//manachar算法的核心所在
10         else
11             p[i]=1;
12         for(;str[i-p[i]]==str[i+p[i]];p[i]++)
13         {
14             if(p[i]+i>mx)
15             {
16                 mx=p[i]+i;
17                 id=i;
18             }
19         }
20         maxn=max(p[i],maxn);
21     }
22     return maxn-1;
23 }
View Code

AC代码：

技术分享 
 1 #include <iostream>
 2 #include<cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cmath>
 6 using namespace std;
 7 char s[110005],str[300000];
 8 int p[300000];
 9 int manachar(int len)
10 {
11     int maxn,mx,id;
12     maxn=mx=id=0;
13     memset(p,0,sizeof(p));
14     for(int i=1;i<len;i++)
15     {
16         if(mx>i)
17             p[i]=min(p[id*2-i],mx-i);
18         else
19             p[i]=1;
20         for(;str[i-p[i]]==str[i+p[i]];p[i]++)
21         {
22             if(p[i]+i>mx)
23             {
24                 mx=p[i]+i;
25                 id=i;
26             }
27         }
28         maxn=max(p[i],maxn);
29     }
30     printf("%d\n",maxn-1);
31     return 0;
32 }
33 int main()
34 {
35     while(~scanf("%s",s))
36     {
37         str[0]=‘$‘,str[1]=‘#‘;
38         int len=strlen(s);
39         for(int i=0;i<len;i++)
40         {
41             str[i*2+2]=s[i];
42             str[i*2+3]=‘#‘;
43         }
44         str[len*2+2]=‘\0‘;
45         manachar(len*2+2);
46     }
47     return 0;
48 }
View Code

 

hdu--3068 最长回文串（manachar模板）


联系
我们