首页 > 代码库 > Ural 1297 Palindrome 【最长回文子串】
Ural 1297 Palindrome 【最长回文子串】
最长回文子串 相关资料：
1、暴力法
2、动态规划
3、中心扩展
4、Manacher法 http://blog.csdn.net/ywhorizen/article/details/6629268
http://blog.csdn.net/kangroger/article/details/37742639
在看后缀数组的时候碰到的这道题目
不过没用后缀数组写出来= = 用了一个很暴力的做法卡进了1 s
Source Code:
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler#include <stdio.h>#include <iostream>#include <string>#include <algorithm>using namespace std;string a, res, tmp1, tmp2;int ans;int main(){ int i, j, k, t, n, m; while(cin >> a){ ans = 1; int len = a.size(); bool flag = false; for(i = 0; i < len; ++i){ if(len - i < ans) break; for(j = len - i; j >= 1; --j){ tmp1 = a.substr(i, j); tmp2 = tmp1; reverse(tmp1.begin(), tmp1.end());a if(!flag){ if(tmp1.compare(tmp2) == 0 && j >= ans){ flag = true; res = tmp1; ans = j; break; } } else{ if(tmp1.compare(tmp2) == 0 && j > ans){ flag = true; res = tmp1; ans = j; break; } } } } cout << res << endl; } return 0;}531 ms 是可以过= = 不过大家用后缀数组都是15MS 过的，有点不好意思啊
Ural 1297 Palindrome 【最长回文子串】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。