发布于 2014-10-22 03:26:35 | 179 次阅读 | 评论: 0 | 来源: 网友投递
百度(Baidu)中文搜索引擎
百度（Nasdaq简称：BIDU）是全球最大的中文搜索引擎，2000年1月由李彦宏、徐勇两人创立于北京中关村，致力于向人们提供“简单，可依赖”的信息获取方式。“百度”二字源于中国宋朝词人辛弃疾的《青玉案·元夕》词句“众里寻他千百度”，象征着百度对中文信息检索技术的执著追求。
给你一个字符串，找出该字符串中对称的子字符串的最大长度。即求最大回文串。
即不使用技巧，穷举所有可能。时间复杂度为O(n^3)（时间上最长，不推荐使用），空间复杂度为O(1)。
本思路是从最大长度的字串开始，而不是从最小开始。假如说给定的字符串为len，先遍历长度为len的字串是否为回文串，如果是停止，
如果不是遍历长度为len-1的字串是否是回文串，一次类推。
#include <iostream>
using namespace std;
//是否是回文串
bool IsPalindromeSubNumber(string num){
int len = num.length();
for(int i = 0,j=len-1;i < j;i++,j--){
if(num[i] != num[j]){
return false;
}
}
return true;
}
void MaxSubPalindromeNumber(string num){
bool result;
bool flag = false;
int len = num.length();
//遍历字串的长度
for(int i = len;i > 0;i--){
//遍历字串的起始位置
for(int j = 0;j+i <= len;j++){
result = IsPalindromeSubNumber(num.substr(j,i));
if(result){
flag = true;
cout<<num.substr(j,i)<<endl;
}
}
if(flag){
break;
}
}
}
int main(){
string num = "djdslkAABCDEAfjdl1234321skjflkdsjfkldsababasdlkfjsdwieowowwpw";
MaxSubPalindromeNumber(num);
return 0;
}
#include<string>
#include<iostream>
using namespace std;
string IsPalindromeNumber(string str){
int maxLen = 1,start = 0;
int len = str.length();
string s = str;
int left,right;
for(int i = 0;i < len;i++){
//奇数字串
int oddLen = 1;
left = i-1;
right = i+1;
while(left >= 0 && right < len && str[left] == str[right]){
left--;
right++;
oddLen += 2;
}
//更新最大长度
if(oddLen > maxLen){
maxLen = oddLen;
//记录当前最大回文串的起始位置
start = left+1;
}
//偶数字串
left = i;
right = i+1;
int evenLen = 0;
while(left >= 0 && right < len && str[left] == str[right]){
left--;
right++;
evenLen += 2;
}
//更新最大长度
if(evenLen > maxLen){
maxLen = evenLen;
//记录当前最大回文串的起始位置
start = left+1;
}
}
return str.substr(start,maxLen);
}
int main(){
string str="djdslkAABCDEAfjdl1234321skjflkdsjfkldsababasdlkfjsdwieowowwpw";
string s=IsPalindromeNumber(str);
cout<<s<<endl;
return 0;
}