[UVa] 12833 - Daily Potato

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 12833 - Daily Potato
Source            : UVa Online Judge
Category          : Data Structure
Algorithm         : Palindromic Tree
Verdict           : Accepted



#include <bits/stdc++.h>  
  
using namespace std;  
  
static const int maxn = 105000;  
  
struct segmentTree  
{  
    int arr[26];  
    void assignLeaf(int val)  
    {  
        fill(begin(arr), end(arr), 0);  
        arr[val] = 1;  
    }  
    void marge(segmentTree &l, segmentTree &r)  
    {  
        for (int i = 0; i < 26; i++) arr[i] = l.arr[i] + r.arr[i];  
    }  
} Tree[maxn << 2];  
  
char s[maxn];  
char qs[maxn];  
  
inline void build(int node, int a, int b)  
{  
    if (a == b)  
    {  
        Tree[node].assignLeaf(s[a] - 'a');  
        return;  
    }  
    int lft = node << 1;  
    int rgt = lft | 1;  
    int mid = (a + b) >> 1;  
    build(lft, a, mid);  
    build(rgt, mid+1, b);  
    Tree[node].marge(Tree[lft], Tree[rgt]);  
}  
  
inline int query(int node, int a, int b, int i, int j, int val)  
{  
    if (a > b || a > j || b < i) return 0;  
    if (a >= i && b <= j) return Tree[node].arr[val];  
    int lft = node << 1;  
    int rgt = lft | 1;  
    int mid = (a + b) >> 1;  
    int p1 = query(lft, a, mid, i, j, val);  
    int p2 = query(rgt, mid+1, b, i, j, val);  
    return p1+p2;  
}  
  
struct node  
{  
    int next[26];  
    int len;  
    int sufflink;  
    int pos;  
    vector <int> backlink;  
    int extraBacklink;  
} tree[maxn];  
  
int len;  
int num;  
int suff;  
int ans[26][maxn];  
  
inline bool addLetter(int pos)  
{  
    int cur = suff;  
    int 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].extraBacklink += 1;  
        return false;  
    }  
    num++;  
    suff = num;  
    tree[num].len = tree[cur].len + 2;  
    tree[num].pos = pos;  
    tree[cur].next[let] = num;  
    if (tree[num].len == 1)  
    {  
        tree[num].sufflink = 2;  
        return true;  
    }  
    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];  
            tree[tree[cur].next[let]].backlink.push_back(num);  
            break;  
        }  
    }  
    return true;  
}  
  
inline void initTree()  
{  
    num = 2;  
    suff = 2;  
    tree[1].len = -1;  
    tree[1].sufflink = 1;  
    tree[2].len = 0;  
    tree[2].sufflink = 1;  
    for (int i = 0; i < maxn; i++)  
    {  
        fill(begin(tree[i].next), end(tree[i].next), 0);  
        tree[i].backlink.clear();  
        tree[i].extraBacklink = 0;  
    }  
    memset(ans, 0, sizeof(ans));  
}  
  
/* 
  TLE 
void getAns(int suf, int pos) 
{ 
    int letter = s[pos] - 'a'; 
    while (true) 
    { 
        int lenPal = tree[suf].len; 
        int start = tree[suf].pos-lenPal+1; 
        int endd = tree[suf].pos; 
        int cnt = query(1, 0, len-1, start, endd, letter); 
        ans[letter][cnt] += 1; 
        //printf("pos=%d | letter=%d | start=%d, endd=%d | cnt=%d | ans[%d][%d]=%d\n", pos, letter, start, endd, cnt, letter, cnt, ans[letter][cnt] ); 
        suf = tree[suf].sufflink; 
        if (suf <= 2) break; 
    } 
} 
*/  
  
int subtree[maxn];  
  
inline void dfs(int suf, int letter)  
{  
    subtree[suf] = 1;  
    for (int nextNode : tree[suf].backlink)  
    {  
        dfs(nextNode, letter);  
        subtree[suf] += subtree[nextNode] + tree[nextNode].extraBacklink;  
    }  
    int lenPal = tree[suf].len;  
    int numBacklink = subtree[suf] + tree[suf].extraBacklink;  
    int start = tree[suf].pos - lenPal + 1;  
    int endd = tree[suf].pos;  
    int cnt = query(1, 0, len-1, start, endd, letter);  
    ans[letter][cnt] += numBacklink;  
}  
  
int main()  
{  
    //freopen("in.txt", "r", stdin);  
  
    int tc;  
    scanf("%d", &tc);  
    for (int tcase = 1; tcase <= tc; tcase++)  
    {  
        scanf("%d", &len);  
        scanf("%s", s);  
        build(1, 0, len-1);  
        initTree();  
        for (int i = 0; i < len; i++) addLetter(i);  
        for (int i = 0; i < 26; i++) dfs(tree[1].next[i], i);  
        int q;  
        scanf("%d", &q);  
        scanf("%s", qs);  
        printf("Case %d:\n", tcase);  
        for (int i = 0; i < q; i++)  
        {  
            int cnt;  
            scanf("%d", &cnt);  
            int letter = qs[i] - 'a';  
            if (cnt > len) puts("0");  
            else printf("%d\n", ans[letter][cnt]);  
        }  
    }  
}