首页 > 试题广场 >

长度为N（N很大）的字符串，求字符串中的最大回文字串

[问答题]
长度为N（N很大）的字符串，求字符串中的最大回文字串
添加回答
onizuka头像 onizuka
将字符串翻过来，与原来字符串计算编辑距离，为最大回文串长度。O（n*n）
发表于 2016-09-10 15:16:51 回复(0)
offer加加头像 offer加加
建议去看看 manacher算法。时间复杂度O(n)
发表于 2016-08-29 11:45:30 回复(0)
Russel头像 Russel 
中心扩展法：（考虑奇数长、偶数长）
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)
提交观点

问题信息

动态规划 字符串 复杂度 百度
上传者：朕翻爱妃牌
难度：
4条回答 8271浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号