i3geek.com
闫庚哲的个人博客

1013 最长回文子串【腾讯2013年实习生招聘二面面试题】

进入OJ

Description

回文串就是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。
回文子串,顾名思义,即字符串中满足回文性质的子串。
给出一个只由小写英文字符a,b,c…x,y,z组成的字符串,请输出其中最长的回文子串的长度。

Input

输入包含多个测试用例,每组测试用例输入一行由小写英文字符a,b,c…x,y,z组成的字符串,字符串的长度不大于200000。

Output

对于每组测试用例,输出一个整数,表示该组测试用例的字符串中所包含的的最长回文子串的长度。

Sample Input

abab
bbbb
abba

Sample Output

3
4
4

Hint

背包问题:http://www.i3geek.com/?p=523

Source

腾讯2013年实习生招聘二面面试题

Answer


 

方法一:动态规划

P(i,j)为1时代表字符串Si到Sj是一个回文,为0时代表字符串Si到Sj不是一个回文。

P(i,j)= P(i+1,j-1)(如果S[i] = S[j])。这是动态规划的状态转移方程。

P(i,i)= 1,P(i,i+1)= if(S[i]= S[i+1])

string longestPalindromeDP(string s) {
  int n = s.length();

  int longestBegin = 0;

  int maxLen = 1;

  bool table[1000][1000] = {false};

  for (int i = 0; i < n; i++) {

    table[i][i] = true;   //前期的初始化

  }

  for (int i = 0; i < n-1; i++) {

    if (s[i] == s[i+1]) {

      table[i][i+1] = true; //前期的初始化

      longestBegin = i;

      maxLen = 2;

    }

  }

  for (int len = 3; len <= n; len++) {

    for (int i = 0; i < n-len+1; i++) {

      int j = i+len-1;

      if (s[i] == s[j] && table[i+1][j-1]) {

        table[i][j] = true;

        longestBegin = i;

        maxLen = len;

      }

    }

  }

  return s.substr(longestBegin, maxLen);

}

方法二 Manacher

#include<vector>
#include<iostream>
using namespace std;

const int N=300010;
int n, p[N];
char s[N], str[N];

#define _min(x, y) ((x)<(y)?(x):(y))

void kp()
{
    int i;
    int mx = 0;
    int id;
    for(i=n; str[i]!=0; i++)
        str[i] = 0; //没有这一句有问题。。就过不了ural1297,比如数据:ababa aba
    for(i=1; i<n; i++)
    {
        if( mx > i )
            p[i] = _min( p[2*id-i], p[id]+id-i );
        else
            p[i] = 1;
        for(; str[i+p[i]] == str[i-p[i]]; p[i]++)
            ;
        if( p[i] + i > mx )
        {
            mx = p[i] + i;
            id = i;
        }
    }
}

void init()
{
 int i, j, k;
 str[0] = '$';
 str[1] = '#';
 for(i=0; i<n; i++)
 {
  str[i*2+2] = s[i];
  str[i*2+3] = '#';
 }
 n = n*2+2;
 s[n] = 0;
}

int main()
{
 int i, ans;
 while(scanf("%s", s)!=EOF)
 {
  n = strlen(s);
  init();
  kp();
  ans = 0;
  for(i=0; i<n; i++)
   if(p[i]>ans)
    ans = p[i];
  printf("%d\n", ans-1);
 }
 return 0;
}

方法三 简化Manacher

主要思想是从左到右处理字符串,求每个位置为中心的两端对称的最大半径。

void Manacher(char s[],int n,int radius[])
{
      int i,j;
      for(i=1;i<n;i++) radius[i]=1;
      for(i=2;i<n;i=j)
      {
           while(s[i-radius[i]]==s[i+radius[i]]) radius[i]++;  //求以当前位置为中心的最大对称半径
           int rBnd=i+radius[i];
           for(j=i+1;j<rBnd;j++) //对当前位置半径覆盖范围内右边的位置进行处理
           {
                 /*
                 ** 如果位置j以位置i为中心的对称位置k=i-(j-i),它的最大半径被i的半径包含,那么j的最大半径就等于radius[k],根据对称性;
                 ** 否则,也就是位置k的最长回文串的左端等于或者向左超过以i为中心的回文串的左端,那么j的最大半径至少为i+radius[i]-j;
                 ** 这样,i~j中间位置的最大半径都求出来了,i下次直接从j开始扩展最大半径
                 */
                 if(j+radius[i-(j-i)]<rBnd)  
                      radius[j]=radius[i-(j-i)];
                 else
                 {
                      radius[j]=rBnd-j;
                      break;

                 }
           }
      }
}

①统一字符串的奇偶数量

先在每两个相邻字符中间插入一个分隔符,当然这个分隔符要在原串中没有出现过。一般可以用‘#’分隔。这样就非常巧妙的将奇数长度回文串与偶数长度回文串统一起来考虑了。

②遍历每个字符的最大半径

用一个辅助数组P记录以每个字符为中心的最长回文串的信息。

Code

#include <iostream>
#include<stdio.h>
#include <string.h>
using namespace std;
char temp[200011];
char str[400011];
int p[400011];
int main()
{
    while(scanf("%s",&temp)!=EOF)
    {
        int m;
        int str_length = strlen(temp);

        for(m = 0;m<str_length;m++)
        {
            str[m*2]='#';
            str[m*2+1]=temp[m];
        }

        str[m*2]='#';

        for(int m = 0;m<str_length*2;m++)
        {
            p[m]=1;
            for(int n=1;n<m+1;n++)
            {
                if(str[m-n] == str[m+n])
                    p[m]++;
                else break;
            }
        }

        int max = p[0];
        for(int m = 1;m<str_length*2;m++)
        {

            if(max<p[m])
            {
                max = p[m];
            }
        }

        printf("%d\n",max-1);
    }
}

 

赞(0)
未经允许不得转载:爱上极客 » 1013 最长回文子串【腾讯2013年实习生招聘二面面试题】
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址