LeetCode/Shortest_Palindrome_2.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
//https://leetcode.com/problems/shortest-palindrome/
#include <bits/stdc++.h>
#include <iostream>
#include <sstream>
#include <string>

using namespace std;
#define maxn 50001

string s = "aacecaaa";
//string s = "abcabe";
//string s="abcabffabcabc";

int nnext[maxn];

void kmp_pre(const string &s) {
    int sz = s.length();
    cout<<"sz: "<<sz<<endl;
    int id_1=1;
    int id_s=0;
    nnext[0] = 0;
    while(id_1<sz){
        if(s[id_1] == s[id_s]){
            id_s++;
            nnext[id_1] = id_s;
            id_1++;
        }else if(id_s >0){
            id_s = nnext[id_s];
        }else{
            nnext[id_1] = 0;
            id_1++;
        }
    }
    cout<<"kmp: ";
    for(int i=0;i<sz;i++){
        cout<<nnext[i];
    }
    cout<<endl;
}


int main(){

    string ans="";
    string tmp;

    int sz = s.length();
    int start;
    tmp = s;
    tmp = s + string(tmp.rbegin(), tmp.rend());
    int t_sz = tmp.length();

    kmp_pre(s);
    //  cout<<"tmp: "<<tmp<<endl;
    int j=0;
    //arr[0] = -1;
    for(int i=sz;i<t_sz;i++) {
        if(tmp[i]==tmp[0]){
            start = i;
            int l = 1;
            int k = i+1;
            for(;k<tmp.length()&&tmp[k]==tmp[l++];k++){}
            if(k==tmp.length()){
                break;
            }
        }
    }

    for(int i=sz;i<start;i++){
        ans += tmp[i];
    }
    //cout<<"start: "<<start<<endl;
    ans += s;
    cout<<ans<<endl;
    //return ans;

}