首页 > 试题广场 > 长度为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 关注
微 博:牛客网 关注

扫一扫,把题目装进口袋