CodeStream

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  12 随笔 :: 0 文章 :: 6 评论 :: 0 Trackbacks


题目链接......

最长回文

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


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
 

Recommend
lcy

代码:

#include <iostream>
#include 
<cstdio>
#include 
<string>
#include 
<cstring>
using namespace std;

#define max_size 110010

int next1[max_size];
int next2[max_size];
int next[max_size];
int ans;

char a[max_size];
char b[max_size];

void getNext1(int n)
{
     
int i, j, k;
     next[
0= n;
     j 
= 0;
     
while (j + 1 < n && b[j] == b[j+1])j++;
     next[
1= j;
     k 
= 1;
     
for (i = 2; i < n; i++)
     {
         
if (next[i-k] + i < next[k] + k)
            next[i] 
= next[i-k];
         
else
         {
             j 
= next[k] + k - i;
             
if (j < 0)j = 0;
             
while (i+< n && b[j] == b[i+j])j++;
             next[i] 
= j;
             k 
= i;
         }
     }
}

void getNext2(char *s, int *nexts, int n, int m)
{
     getNext1(m);
     
int i, j, k;
     j 
= 0;
     k 
= 0;
     
while (s[j] == b[j])j++;
     nexts[
0= j;
     
     
for (i = 1; i < n; i++)
     {
         
if (next[i-k] + i < nexts[k] + k)
             nexts[i] 
= next[i-k];
         
else
         {
             j 
= nexts[k] + k - i;
             
if (j < 0) j = 0;
             
while (i + j < n && s[i+j] == b[j])j++;
             nexts[i] 
= j;
             k 
= i;
         }
     }
}

void res(char *s, int n)
{
     
char st;
     
int len = (n>>1);
     
for (int i = 0; i < len; i++)
     {
         st 
= s[i];
         s[i] 
= s[n-i-1];
         s[n
-i-1= st;
     }
}

void find(char *s, int n)
{
     
if (ans >= n || n < 2)return;
     
int i, k, x;
     
int mid;
     
     mid 
= (n>>1);
     
     
for (i = mid; i < n; i++)b[i-mid] = s[i];
     b[i
-mid] = 0;
     res(s, n);
     getNext2(s, next1, n, i
-mid);
     
     res(s, n);
     
for (i = 0; i < mid; i++)
       b[i] 
= s[mid-i-1];
     b[i] 
= 0;
     getNext2(s, next2, n, mid);
     
     next1[n] 
= next2[n] = 0;
     
     
for (i = 0; i < mid; i++)
     {
         
if (next2[i] >= mid - i)
         {
             x 
= mid - i + 2 * next1[n-i];
             
if (ans < x)ans = x;
         }
     }
     
for (i = mid; i < n; i++)
     {
         
if (next1[n-i] >= i - mid)
         {
             x 
= i - mid + 2*next2[i];
             
if (ans < x) ans = x;
         }
     }
     find(s, mid);
     find(s
+mid, n-mid);
}

int main()
{
    
int  n;
    
while (scanf("%s", a) != EOF)
    {
          n 
= strlen(a);
          ans 
= 1;
          find(a, n);
          printf(
"%d\n", ans);
    }
    
return 0;
}

posted on 2011-05-13 15:03 CodeStream 阅读(949) 评论(1)  编辑 收藏 引用

评论

# re: hdu 3068 最长回文 扩展KMP 2013-04-10 20:12 膜拜者
你这里是怎么来的?能细讲下吗?谢谢
for (i = 0; i < mid; i++)
{
if (next2[i] >= mid - i)
{
x = mid - i + 2 * next1[n-i];
if (ans < x)ans = x;
}
}
for (i = mid; i < n; i++)
{
if (next1[n-i] >= i - mid)
{
x = i - mid + 2*next2[i];
if (ans < x) ans = x;
}
}  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理