首页 > 试题广场 > 长度为N(N很大)的字符串,求字符串中的最大回文字串
[问答题]
长度为N(N很大)的字符串,求字符串中的最大回文字串

4个回答

添加回答
将字符串翻过来,与原来字符串计算编辑距离,为最大回文串长度。O(n*n)
发表于 2016-09-10 15:16:51 回复(0)
建议去看看 manacher算法。时间复杂度O(n)
发表于 2016-08-29 11:45:30 回复(0)
中心扩展法:(考虑奇数长、偶数长)
string LongestPalindrome(string s)
{
  int n = s.size();
  if (n <= 1) return s;
  int len = 1;
  string res = s.substr(0, 1);

  for (int i = 1; i <= n-2; i++)
  {
     int j = 1;
     for (; (i-j) >= 0 && (i+j) <= n-1; j++)
       if (s[i-j] != s[i+j])
          break;
     if (2*j - 1 > len)
     {
        len = 2*j - 1;
        res = s.substr(i-j+1, 2*i-1);
     }
   }
  
  for (int i = 0; i <= n-2; i++)
  {
    if (s[i] != s[i+1])
      continue;
    int j = 1;
    for (; (i-j) >= 0 && (i+1+j) <= n-1; j++)
      if (s[i-j] != s[i+1+j])
        break;
    if (2*j > len)
    {
      len = 2*j;
      res = s.substr(i-j+1, 2*j);
     }
   }
   return res;
}

编辑于 2016-06-24 19:11:16 回复(2)
顺序扫描字符串,对每个字符从中间向两边展开,o(n2)复杂度
发表于 2014-10-14 18:36:59 回复(0)
牛客网,程序员必备求职神器
QQ群:169195721
微 信:www_nowcoder_com 关注
微 博:牛客网 关注

扫一扫,把题目装进口袋