fork download

copy

// odd[i] means palindrome starts at i - odd[i] and ends at i + odd[i]
// even[i] means palindrome starts at i - even[i] - 1, and ends at i + even[i] iff even[i] != 0
void manacher(const string &s, vector<int> &odd, vector<int> &even)
{
    int n = sz(s);
    odd.clear();
    even.clear();
    odd.resize(n);
    even.resize(n);
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 1 : min(odd[l + r - i], r - i + 1);
        while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
            k++;
        }
        odd[i] = --k;
        if (i + k > r) {
            l = i - k;
            r = i + k;
        }
    }
 
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 0 : min(even[l + r - i + 1], r - i + 1);
        while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
            k++;
        }
        even[i] = k--;
        if (i + k > r) {
            l = i - k - 1;
            r = i + k ;
        }
    }
}
 
// strt[i] -> how many palindromes start at i
// fnsh[i] -> how many palindromes end at i
// countCover[i] -> how many palindromes cover i
const int MAX_N = 2e6 + 5;
long long strt[MAX_N], fnsh[MAX_N], countCover[MAX_N];
void calcCover(const vector<int> &odd, const vector<int> &even)
{
    int n = odd.size();
    for (int i = 0; i < n; ++i)
    {
        // odd
        int st = i - odd[i], en = i + odd[i];
        fnsh[i]++, fnsh[en + 1]--;
        strt[st]++, strt[i + 1]--;
 
 
        if (even[i])
        {
            st = i - even[i], en = i + even[i] - 1;
            fnsh[i]++, fnsh[en + 1]--;
            strt[st]++, strt[i]--;
        }
    }
 
    for (int i = 1; i < n; ++i)
    {
        strt[i] += strt[i - 1];
        fnsh[i] += fnsh[i - 1];
    }
    long long activePalindromes = 0;
    for (int i = 0; i < n; ++i)
    {
        activePalindromes += strt[i];
        countCover[i] = activePalindromes;
        activePalindromes -= fnsh[i];
    }
}

prog.cpp:3:21: error: ‘string’ does not name a type; did you mean ‘struct’?
 void manacher(const string &s, vector<int> &odd, vector<int> &even)
                     ^~~~~~
                     struct
prog.cpp:3:32: error: ‘vector’ has not been declared
 void manacher(const string &s, vector<int> &odd, vector<int> &even)
                                ^~~~~~
prog.cpp:3:38: error: expected ‘,’ or ‘...’ before ‘<’ token
 void manacher(const string &s, vector<int> &odd, vector<int> &even)
                                      ^
prog.cpp: In function ‘void manacher(const int&, int)’:
prog.cpp:5:13: error: ‘sz’ was not declared in this scope
     int n = sz(s);
             ^~
prog.cpp:5:13: note: suggested alternative: ‘s’
     int n = sz(s);
             ^~
             s
prog.cpp:6:5: error: ‘odd’ was not declared in this scope
     odd.clear();
     ^~~
prog.cpp:7:5: error: ‘even’ was not declared in this scope
     even.clear();
     ^~~~
prog.cpp:11:31: error: ‘min’ was not declared in this scope
         int k = (i > r) ? 1 : min(odd[l + r - i], r - i + 1);
                               ^~~
prog.cpp:12:50: error: invalid types ‘const int[int]’ for array subscript
         while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
                                                  ^
prog.cpp:12:62: error: invalid types ‘const int[int]’ for array subscript
         while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
                                                              ^
prog.cpp:23:31: error: ‘min’ was not declared in this scope
         int k = (i > r) ? 0 : min(even[l + r - i + 1], r - i + 1);
                               ^~~
prog.cpp:24:58: error: invalid types ‘const int[int]’ for array subscript
         while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
                                                          ^
prog.cpp:24:70: error: invalid types ‘const int[int]’ for array subscript
         while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
                                                                      ^
prog.cpp: At global scope:
prog.cpp:40:22: error: ‘vector’ does not name a type
 void calcCover(const vector<int> &odd, const vector<int> &even)
                      ^~~~~~
prog.cpp:40:28: error: expected ‘,’ or ‘...’ before ‘<’ token
 void calcCover(const vector<int> &odd, const vector<int> &even)
                            ^
prog.cpp: In function ‘void calcCover(int)’:
prog.cpp:42:13: error: ‘odd’ was not declared in this scope
     int n = odd.size();
             ^~~
prog.cpp:47:25: error: ‘en’ was not declared in this scope
         fnsh[i]++, fnsh[en + 1]--;
                         ^~
prog.cpp:47:25: note: suggested alternative: ‘n’
         fnsh[i]++, fnsh[en + 1]--;
                         ^~
                         n
prog.cpp:51:13: error: ‘even’ was not declared in this scope
         if (even[i])
             ^~~~

Standard output is empty