-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path5.cpp
More file actions
52 lines (48 loc) · 1.44 KB
/
5.cpp
File metadata and controls
52 lines (48 loc) · 1.44 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/*************************************************************************
> File Name: 5.cpp
> Author: Alan
> Mail: [email protected]
> Created Time: Mon 09 Nov 2015 08:03:56 PM CST
> Problem Name: Longest Palindromic Substring My Submissions Question
> Difficulty: Medium
> Description:
Given a string S, find the longest palindromic substring in S. You may assume that the maximum
length of S is 1000, and there exists one unique longest palindromic substring.
************************************************************************/
#include<iostream>
#include<cstring>
using namespace std;
class Solution
{
public:
string longestPalindrome(string s)
{
const int len = s.size();
bool p[len][len];
memset(p, false, len * len);
int max_len = 1, start = 0;
for(int j = 0; j < len; j++)
{
p[j][j] = true;
for(int i = 0; i < j; i++)
{
p[i][j] = (s[i] == s[j] && (j - i < 2 || p[i + 1][j - 1]));
if(p[i][j] && max_len < (j - i + 1))
{
max_len = j - i + 1;
start = i;
}
}
}
return s.substr(start, max_len);
}
};
int main()
{
string s
{
"abcbacd"
};
Solution sol = Solution();
cout << "The longest palindromic substring in the string is: " << sol.longestPalindrome(s) << endl;
}