c++

include

// #include "testlib.h" using namespace std ;

define ft first

define sd second

define pb push_back

define all(x) x.begin(),x.end()

define ll long long int

define vi vector

define vii vector >

define pii pair

define plii pair, int>

define piii pair

define viii vector >

define vl vector

define vll vector >

define pll pair

define pli pair

define mp make_pair

define ms(x, v) memset(x, v, sizeof x)

define sc1(x) scanf("%d",&x)

define sc2(x,y) scanf("%d%d",&x,&y)

define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)

define scll1(x) scanf("%lld",&x)

define scll2(x,y) scanf("%lld%lld",&x,&y)

define scll3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)

define pr1(x) printf("%d\n",x)

define pr2(x,y) printf("%d %d\n",x,y)

define pr3(x,y,z) printf("%d %d %d\n",x,y,z)

define prll1(x) printf("%lld\n",x)

define prll2(x,y) printf("%lld %lld\n",x,y)

define prll3(x,y,z) printf("%lld %lld %lld\n",x,y,z)

define pr_vec(v) for(int i=0;i

define f_in(st) freopen(st,"r",stdin)

define f_out(st) freopen(st,"w",stdout)

define fr(i, a, b) for(i=a; i<=b; i++)

define fb(i, a, b) for(i=a; i>=b; i--)

define ASST(x, l, r) assert( x <= r && x >= l )

include

const int MAXN = 105000;

struct node { int next[26]; int len; int sufflink; int num, l, r; };

int len; char s[MAXN]; node tree[MAXN]; int num; // node 1 - root with len -1, node 2 - root with len 0 int suff; // max suffix palindrome long long ans; vi adj[ MAXN ]; viii A; int n, q; bool addLetter(int pos) { int cur = suff, curlen = 0; int let = s[pos] - 'a';

while (true) {
    curlen = tree[cur].len;
    if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])     
        break;  
    cur = tree[cur].sufflink;
}       
if (tree[cur].next[let]) {  
    suff = tree[cur].next[let];
    tree[suff].num ++;
    return false;
}

num++;
suff = num;
tree[num].len = tree[cur].len + 2;
tree[num].r = pos;
tree[num].l = pos - tree[num].len + 1; 
tree[cur].next[let] = num;
if (tree[num].len == 1) {
    tree[num].sufflink = 2;
    tree[num].num = 1;
    return true;
}

tree[num].num ++;
while (true) {
    cur = tree[cur].sufflink;
    curlen = tree[cur].len;
    if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
        tree[num].sufflink = tree[cur].next[let];
        break;
    }       
}
return true;

}

void initTree() { num = 2; suff = 2; tree[1].len = -1; tree[1].sufflink = 1; tree[2].len = 0; tree[2].sufflink = 1; tree[1].num = tree[2].num = 0; }

void dfs( int u ) { for( auto it: adj[u] ) { dfs(it); tree[u].num += tree[it].num; } }

int iSA[MAXN], SA[MAXN]; int cnt[MAXN], next_gen[MAXN], lcp[ MAXN ], LCP[MAXN][22]; //internal bool bh[MAXN], b2h[MAXN],m_arr[MAXN];

bool smaller_first_char(int a, int b){ return s[a] < s[b]; }

void SuffixSort(int n) { for (int i=0; i= 0){ int head = iSA[s]; iSA[s] = head + cnt[head]++; b2h[iSA[s]] = true; } } for (int j = i; j < next_gen[i]; ++j){ int s = SA[j] - h; if (s >= 0 && b2h[iSA[s]]){ for (int k = iSA[s]+1; !bh[k] && b2h[k]; k++) b2h[k] = false; } } } for (int i=0; i

void InitLCP(int n) { for (int i=0; i 0) { int j = SA[iSA[i]-1]; while (i + h < n && j + h < n && s[i+h] == s[j+h]) h++; lcp[iSA[i]] = h; if (h > 0) h--; } } }

void ConstructLCP() { InitLCP( len ); for(int i = 0;i

int GetLCP(int x, int y) { if(x == y) return len-SA[x]; if(x > y) swap(x,y); int log = 0; while((1<

bool cmp(const piii &a, const piii &b) { int l1, r1, l2, r2, len1, len2; l1 = a.ft.ft; r1 = a.ft.sd; l2 = b.ft.ft; r2 = b.ft.sd; len1 = r1 - l1 + 1; len2 = r2 - l2 + 1; int res = 0; int v = GetLCP(iSA[l1], iSA[l2]); if(v >= min(len1, len2)) { res = (len1 < len2); } else { res = (iSA[l1] < iSA[l2]); } return res; }

int P[MAXN], HashF[MAXN], HashR[MAXN]; class RollingHash { public: RollingHash() { prime = 100001; mod1 = 1000000007; mod2 = 1897266401; P[0] = 1; for(int i=1; i

    void Construct() {
        HashF[0] = HashR[ len+1 ] = 0;
        for(int i=1; i<=len; i++) {
            HashF[i] = ( 1LL * HashF[i-1] * prime + s[i-1] ) % mod1;
            HashR[len-i+1] = ( 1LL * HashR[len-i+2] * prime + s[ len - i ] ) % mod1; 
        }
    }

    int GetForwardHash( int l, int r ) {
        if( l == 1 ) return HashF[r];
        int hash = HashF[r] - 1LL * HashF[l-1] * P[ r - l + 1 ] % mod1;
        if( hash < 0 ) hash += mod1;
        return hash;
    }
    int GetBackwardHash( int l, int r ) {
        if( r == len ) return HashR[l];
        int hash = HashR[l] - 1LL * HashR[r+1] * P[ r - l + 1 ] % mod1;
        if( hash < 0 ) hash += mod1;
        return hash;
    }
    bool IsPalin( int l, int r ) {
        if( r < l ) return true;
        return (GetForwardHash(l, r) == GetBackwardHash(l, r));
    }

private:
    int prime, mod1, mod2;

};

int main() {

cin >> n >> q;
cin >> s;
len = n;

initTree();
SuffixSort( len );
ConstructLCP();
for (int i = 0; i < len; i++) {
    addLetter(i);
}

for(int i=2; i<=num; i++) {
    adj[tree[i].sufflink].pb(i);
}

dfs(1);

for(int i=3; i<=num; i++) {
    A.pb(mp(mp(tree[i].l, tree[i].r), tree[i].num));
}

sort(all(A), cmp);
vl bs, has;
RollingHash obj;
obj.Construct();
ll v = 0;
for( auto it: A ) {
    v += it.sd;
    bs.pb( v );
    has.pb(obj.GetForwardHash(it.ft.ft+1, it.ft.sd+1));
}
ll k; 
while( q-- ) {
    cin >> k;
    if( k > v ) cout << -1 << "\n";
    else {
        auto it = lower_bound(all(bs), k);
        cout << has[it-bs.begin()] << "\n";
    }
}
return 0;

}

There are the plenty of applications you can use and fix the problem easily. I also need such stuff and glad to have it here. Please continue with your valuable academized.com reviews sharing please do share such wise helping suggestions always.

here is hackerrank functional palindromes solution

the requirement must be written better. the challenge of this akaton is not making the exercise, but understanding what the writer was thinking

The mistake is in how this problem was written. If you offer one toy dataset and no hints as to edge cases, your writing is shite.