金山办公软件C++开发工程师笔试题(3)

奇数回文串

定义奇数回文串是一个正读和反读都一样的,长度为奇数的字符串,比如“level”或者“non”就是奇数回文串。

请用不高于O(n^2)复杂度(以str.length()为准)的算法写出以下函数的实现代码。

int func(const std::string& str);

 

str中的字符只可能是小写的拉丁字母,该函数的返回值为str中最长的奇数回文子串的长度。 例如: str为“abba”,则函数的返回值为1。

str为“abcba”,则函数的返回值为5。

str为“eabcmcbad”,则函数的返回值为7。

str为“dddcbamabc”,则函数的返回值为7。

str为“cbamabcddd”,则函数的返回值为7。

我的代码

#include<iostream>
using namespace std;

int func(string str){
      int maxi = 0;
      int temp = 0;
      int count = 0;
      for(int i = 0; i < str.length()  ;i++){
            temp = i;
           int j = i;
           j -- ;
           i ++ ;
           while(j >= 0 && i <= str.length()-1 && str[i] == str[j]){
                count = count + 2;
                i++;
                j--;
           }
           if(count > maxi){
            maxi = count;
           }
           count = 0;
           i = temp;
      }
      return maxi+1;
}

int main(){
       string str1 = "abba";
       string str2 = "abcba";
       string str3 = "eabcmcbad";
       string str4 = "dddcbamabc";
       string str5 = "cbamabcddd";
       cout<<func(str1)<<endl;
       cout<<func(str2)<<endl;
       cout<<func(str3)<<endl;
       cout<<func(str4)<<endl;
       cout<<func(str5)<<endl;
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注