competitive-programming/string/lp_substring.cpp at master · lincolncpp/competitive-programming · 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
#include <bits/stdc++.h>

using namespace std;

int main(){

    string s = "kkabacabaxx";
    int n = (int)s.size();

    int best_len = 0;
    int best_l = 0;
    int best_r = 0;
    for(int i = 0;i < n;i++){

        // even length
        int l = i;
        int r = i+1;
        while(l >= 0 && r < n && s[l] == s[r]){
            l--;
            r++;
        }
        int len = r-l-2;
        if (len > best_len){
            best_len = len;
            best_l = l+1;
            best_r = r-1;
        }

        //odd length
        l = i-1;
        r = i+1;
        while(l >= 0 && r < n && s[l] == s[r]){
            l--;
            r++;
        }
        len = r-l-2;
        if (len > best_len){
            best_len = len;
            best_l = l+1;
            best_r = r-1;
        }
    }

    cout << s.substr(best_l, best_r-best_l+1) << endl;

    return 0;
}