LeetCode/Longest_Palindromic_Substring.cpp at master · Wilson1211/LeetCode · GitHub

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
//https://leetcode.com/problems/longest-palindromic-substring/
#include <iostream>
#include <string.h>
#include <limits>
#include <algorithm>
#include <math.h>
#include <bits/stdc++.h>
using namespace std;


int main () {
    string s = "";
    string manacher_str="#";
    int m_len;
    cin >> s;
    if(s.length() == 1) {
        cout<<s<<endl;
        return 0;
    }
    for(int i=0;i<s.length();i++) {
        manacher_str += s[i];
        manacher_str += "#";
    }

    m_len = manacher_str.length();

    int LPS_table[1001] = {};
    LPS_table[0] = 0;

    int center = 1;
    int maxlen = 0;
    int maxright = 0;
    int LPS_center = 1;

    for(int index = 1;index < m_len-1;index++) {
        if(index < maxright) {
            LPS_table[index] = min(LPS_table[2*center-index], maxright-index);
        }
        else{
            LPS_table[index] = 0;
        }

        while((index-LPS_table[index]-1)>=0 && (index + LPS_table[index]+1)<m_len && manacher_str[index-LPS_table[index]-1] == manacher_str[index+LPS_table[index]+1]) {
            LPS_table[index]++;
        }

        if(maxlen < LPS_table[index]) {
            maxlen = LPS_table[index];
            LPS_center = index;
        }

        if(index + LPS_table[index]-1 > maxright) {
            maxright = index+LPS_table[index];
            center = index;
        }

    }

    cout<<"out: ";
    if(LPS_center == 1) {
        cout<<s[0]<<endl;
        return 0;
    }
    for(int i=LPS_center-LPS_table[LPS_center]+1;i<LPS_center+LPS_table[LPS_center];i+=2) {
        cout<<manacher_str[i];
    }
    cout<<endl;

}


/*
"babad"
"cbbd"
"a"
"ac"
*/