Longest Palindromic Substring
Leet Code 比較特別，有點像是要你完成一個 Function ，所以下面的 Code 有在解答下，加上輸入出。
它好像沒給（？）
先附上 的解法，之後再補上更好的。
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
/*
// On Leet Code
// Difficulty: Medium
class Solution {
public:
string longestPalindrome(string s) {
string odds, evens;
//odd
for(int i=0; i!=s.length(); ++i) {
int j=1;
for(; i-j>=0&&i+j<s.length()&&s[i-j]==s[i+j]; ++j);
--j;
if(j*2+1>=odds.length()) {
odds.clear();
odds.insert(odds.end(), s.begin()+i-j, s.begin()+i+j+1);
}
}
//even
for(int i=1; i<s.length(); ++i) {
int l=i-1, r=i;
for(; l>=0&&r<s.length()&&s[l]==s[r]; --l,++r);
if(s[++l]==s[--r]&&r-l+1>=evens.length()) {
evens.clear();
evens.insert(evens.end(), s.begin()+l, s.begin()+r+1);
}
}
return evens.length()>odds.length()?evens:odds;
}
};
*/
#include <bits/stdc++.h>
using namespace std;
string lps(string &s) {
string odds, evens;
//odd
for(int i=0; i!=s.length(); ++i) {
int j=1;
for(; i-j>=0&&i+j<s.length()&&s[i-j]==s[i+j]; ++j);
--j;
if(j*2+1>=odds.length()) {
odds.clear();
odds.insert(odds.end(), s.begin()+i-j, s.begin()+i+j+1);
}
}
//even
for(int i=1; i<s.length(); ++i) {
int l=i-1, r=i;
for(; l>=0&&r<s.length()&&s[l]==s[r]; --l,++r);
if(s[++l]==s[--r]&&r-l+1>=evens.length()) {
evens.clear();
evens.insert(evens.end(), s.begin()+l, s.begin()+r+1);
}
}
return evens.length()>odds.length()?evens:odds;
}
int main(void) {
string input;
cin>>input;
cout<<lps(input)<<endl;
return 0;
}
Hash 版的（寫爛了，反而比較慢） 應該是
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define F first
#define S second
typedef long long int UT;
typedef pair< UT, UT > PII;
const PII p(29,31), q(10000103, 10000121);
const int MAXN(1010);
PII h[MAXN], rh[MAXN], cache[MAXN];
class Solution {
public:
string longestPalindrome(string &s) {
get_pow(cache, p, s.length(), q);//lazy dog
get_hash(s,h); get_hash(s,rh,true);
int lb=0, hb=s.length()/2+3;//No need to warry.
int eoff=-1, ooff=-1;
while(hb - lb > 1) {
int mid=(lb+hb)/2;
int idx = check(s.length(), h, rh, cache[mid*2], mid*2);
if( idx!=-1 ) {
eoff=idx;
lb=mid;
} else hb=mid;
}
int ev=lb;
lb=0, hb=s.length()/2+3;
while(hb - lb > 1) {
int mid=(lb+hb)/2;
int idx = check(s.length(), h, rh, cache[mid*2+1], mid*2+1);
if( idx!=-1 ) {
ooff=idx;
lb=mid;
} else hb=mid;
}
int od=lb;
if(eoff!=-1 && ooff!=-1) {
return od*2+1>ev*2?s.substr(ooff, od*2+1):s.substr(eoff, ev*2);
}
if(eoff!=-1) return s.substr(eoff, ev*2);
if(ooff!=-1) return s.substr(ooff, od*2+1);
return s.substr(0,1);
}
inline void get_hash(string &s, PII *h, bool rev=false) {
h[0].F=h[0].S=h[s.length()+1].S=h[s.length()+1].F=0;
++h; // index is shifted
if(!rev) {
for(int i=0; i!=s.length(); ++i ){
h[i].F = ((h[i-1].F*p.F%q.F)+s[i]+1)%q.F;
h[i].S = ((h[i-1].S*p.S%q.S)+s[i]+1)%q.S;
}
} else { //reverse
for(int i=s.length()-1, j=0; i!=-1; --i, ++j ){
h[j].F = ((h[j-1].F*p.F%q.F)+s[i]+1)%q.F;
h[j].S = ((h[j-1].S*p.S%q.S)+s[i]+1)%q.S;
}
}
}
inline void get_pow(PII *h, const PII base, const int n, const PII P) {
h[0].F=h[0].S=1;
for(int i=1; i<=n; ++i) {
h[i].F = (h[i-1].F*base.F)%P.F;
h[i].S = (h[i-1].S*base.S)%P.S;
}
}
inline int check(const int L, PII *h, PII *rh, PII const &pw, int n) {
if(n>L) return -1;
h++; rh++; //shift index
UT temp1, temp2, temp3, temp4;//Lazy dog...
for(int i=0; i+n-1<L; ++i) {
temp1 = ((q.F - h[i-1].F*pw.F%q.F) + h[i+n-1].F)%q.F;
temp2 = ((q.F - rh[L-i-n-1].F*pw.F%q.F) + rh[L-i-1].F)%q.F;
temp3 = ((q.S - h[i-1].S*pw.S%q.S) + h[i+n-1].S)%q.S;
temp4 = ((q.S - rh[L-i-n-1].S*pw.S%q.S) + rh[L-i-1].S)%q.S;
/*
for(int v=i; v<i+n; ++v) cout<<s[v];
cout << endl;
cout << temp1 << ' ';
cout << temp2 << endl;
cout << temp3 << ' ';
cout << temp4 << endl;
*/
if(temp1==temp2&&temp3==temp4) {
return i;
}
}
return -1;
}
};
int main(void) {
Solution solver;
string s;
cin>>s;
cout<<solver.longestPalindrome(s)<<endl;
return 0;
}
接下來是 的版本， Manacher’s Algorithm 。
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
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string preProcess(string &s) {
if(s.empty()) return "^$";
string res="^";
for(string::size_type i=0; i!=s.length(); ++i) res+="#"+s.substr(i,1);
return res+"#$";
}
string longestPalindrome(string &s) {
string T=preProcess(s);
int L = T.length();
int *p = new int[T.length()];
//fill(p, p+L, 0);
int id=0, ix=0;
for(int i=1; i<L-1; ++i) {
p[i] = (i<ix)? min(p[(id<<1)-i], ix-i) : 0;
while(T[i+p[i]+1]==T[i-p[i]-1]) ++p[i];
if(i+p[i]>ix) { ix=i+p[i]; id=i; }
}
int offset=(int)(max_element(p+1,p+L-1)-p);
int maxL=p[offset];
delete[] p;
return s.substr( (offset-1-maxL)>>1 , maxL);
}
};
int main(void) {
string s;
Solution sol;
cin>>s;
cout<<sol.longestPalindrome(s)<<endl;
return 0;
}