-
Notifications
You must be signed in to change notification settings - Fork 1
/
longestPalindrome.cpp
80 lines (71 loc) · 2.03 KB
/
longestPalindrome.cpp
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <string>
#include <iostream>
using namespace std;
// Could use sliding window of increasing size!
//Expand Around center optimum = TO(n^2) SO(1)
class Solution {
string findNextToLength(string s){
int longest = 0;
string st = s.substr(0,1);
if(s.size()<2)return st;
for(int i = 1;i<s.size();i++){
if(s[i]==s[i-1]){
int length=2;
int dev = 1;
while(i-1-dev>=0 && i+dev<s.size()){
if(s[i-1-dev]==s[i+dev]){
length+=2;
dev++;
}
else break;
}
if(length>longest){
longest=length;
st = s.substr(i-dev,length);
}
}
}
return st;
}
string findCenterLength(string s){
int longest = 0;
string st = s.substr(0,1);
if(s.size()<3)return st;
for(int i = 2;i<s.size();i++){
if(s[i-2]==s[i]){
int length =3;
int dev = 2;
while(i-1-dev>=0 && i + dev <= s.size()){
if(s[i-1-dev]==s[i-1+dev]){
length+=2;
dev++;
}
else break;
}
if(length>longest){
longest = length;
st = s.substr(i-dev,longest);
}
}
}
return st;
}
public:
string longestPalindrome(string s) {
string longestCurr = s.substr(0,1);
int longestLength=0;
//" a s b s d d s b v"
// | |
//" a s b s d s b v"
// i | i
string NextToLength = findNextToLength(s);
string centerLength = findCenterLength(s);
return NextToLength.size() > centerLength.size() ? NextToLength : centerLength;
}};
int main()
{
Solution s;
string test = "xaabacxcabaaxcabaax";
s.longestPalindrome(test);
return 0;
}