// 演算法：線段樹。每個節點存這段的最長同字元段(best)、前綴(pref)、後綴(suf)、
// 長度(len) 與左右端字元(lc/rc)。合併時特別處理「跨越左右邊界」的段。
// Algorithm: segment tree. Each node stores the best single-char run, plus prefix/
// suffix runs, length, and boundary chars, so a run crossing the split is handled.

#include <string.h>   // strlen
#include <stdlib.h>   // malloc / free

// 一個線段樹節點要記錄的所有資訊 / all info a segment-tree node keeps
typedef struct {
    int pref;   // 從左端算起、同字元的最長前綴長度 / longest same-char prefix length
    int suf;    // 到右端為止、同字元的最長後綴長度 / longest same-char suffix length
    int best;   // 這段區間內部的最長同字元段 / best single-char run inside this segment
    int len;    // 這段區間的長度 / length of this segment
    char lc;    // 這段最左邊的字元 / leftmost character of this segment
    char rc;    // 這段最右邊的字元 / rightmost character of this segment
} Node;

// 把左子節點 a 與右子節點 b 合併成父節點 / merge left child a and right child b into a parent
static Node merge(Node a, Node b) {
    Node r;                                 // r 是要回傳的父節點 / r is the parent to return
    r.len = a.len + b.len;                  // 父長度 = 兩段長度相加 / parent length = sum of the two
    r.lc  = a.lc;                           // 父最左字元 = 左子最左字元 / parent's left char = left child's left char
    r.rc  = b.rc;                           // 父最右字元 = 右子最右字元 / parent's right char = right child's right char

    r.pref = a.pref;                        // 前綴預設等於左子的前綴 / prefix defaults to left child's prefix
    // 若左子整段同一字元，且左子右端字元 == 右子左端字元，前綴可延伸進右子
    // If the left child is all one char AND its right char equals the right child's left char, extend
    if (a.pref == a.len && a.rc == b.lc)
        r.pref = a.len + b.pref;            // 吃進右子的前綴 / absorb right child's prefix

    r.suf = b.suf;                          // 後綴預設等於右子的後綴 / suffix defaults to right child's suffix
    // 對稱地：若右子整段同字元，且右子左端 == 左子右端，後綴延伸進左子
    // Symmetric: extend the suffix into the left child when possible
    if (b.suf == b.len && b.lc == a.rc)
        r.suf = b.len + a.suf;              // 吃進左子的後綴 / absorb left child's suffix

    r.best = a.best > b.best ? a.best : b.best;  // 先取兩子答案的較大者 / start from max of children's best
    if (a.rc == b.lc) {                     // 邊界兩字元相同才可能有跨界段 / a crossing run needs matching boundary chars
        int cross = a.suf + b.pref;         // 跨界段 = 左後綴 + 右前綴 / crossing run = left suffix + right prefix
        if (cross > r.best) r.best = cross; // 若更長就更新 / take it if longer
    }
    return r;                               // 回傳合併結果 / return the merged node
}

// 建樹：node 是樹陣列的下標，[l,r] 是這個節點負責的區間
// Build: node is the array index, [l,r] is the range this node covers
static void build(Node* tree, char* s, int node, int l, int r) {
    if (l == r) {                           // 葉子：只負責一個字元 / leaf: covers a single character
        tree[node].pref = tree[node].suf = tree[node].best = tree[node].len = 1;  // 單字元各值皆為 1 / all length-like fields are 1
        tree[node].lc = tree[node].rc = s[l];  // 左右端都是這個字元 / both ends are this character
        return;
    }
    int mid = (l + r) / 2;                  // 取中點把區間對半 / split the range in half at mid
    build(tree, s, 2 * node,     l,     mid);   // 遞迴建左半 (下標 2*node) / build left half (index 2*node)
    build(tree, s, 2 * node + 1, mid + 1, r);   // 遞迴建右半 (下標 2*node+1) / build right half (index 2*node+1)
    tree[node] = merge(tree[2 * node], tree[2 * node + 1]);  // 由兩子合併出本節點 / combine children into this node
}

// 單點更新：把位置 pos 的字元改成 c，並沿路往上重算
// Point update: set the char at position pos to c, then recompute up the path
static void update(Node* tree, int node, int l, int r, int pos, char c) {
    if (l == r) {                           // 到達目標葉子 / reached the target leaf
        tree[node].lc = tree[node].rc = c;  // 更新這個字元 / update the character (len/pref/suf/best stay 1)
        return;
    }
    int mid = (l + r) / 2;                  // 中點 / midpoint
    if (pos <= mid) update(tree, 2 * node,     l,     mid, pos, c);  // 目標在左半就往左走 / go left if pos is in the left half
    else            update(tree, 2 * node + 1, mid + 1, r, pos, c);  // 否則往右走 / otherwise go right
    tree[node] = merge(tree[2 * node], tree[2 * node + 1]);  // 子節點變了，重算本節點 / children changed, recombine this node
}

int* longestRepeating(char* s, char* queryCharacters, int* queryIndices,
                      int queryIndicesSize, int* returnSize) {
    int n = strlen(s);                      // 字串長度 / length of the string
    // 線段樹需要 4*n 個節點才夠用 / a segment tree needs up to 4*n nodes to be safe
    Node* tree = (Node*)malloc(sizeof(Node) * 4 * n);  // malloc 動態配置記憶體 / dynamically allocate memory
    build(tree, s, 1, 0, n - 1);            // 從下標 1 當根、負責 [0, n-1] 建樹 / build from root index 1 over [0, n-1]

    int* ans = (int*)malloc(sizeof(int) * queryIndicesSize);  // 存每次查詢答案 / holds each query's answer
    for (int i = 0; i < queryIndicesSize; i++) {              // 依序處理每個查詢 / process queries in order
        update(tree, 1, 0, n - 1, queryIndices[i], queryCharacters[i]);  // 改一個字元 / apply one character change
        ans[i] = tree[1].best;              // 根節點的 best 就是全字串的答案 / root's best is the whole-string answer
    }

    *returnSize = queryIndicesSize;         // 透過指標回傳陣列長度 / report array length via the out-pointer
    free(tree);                             // 釋放線段樹記憶體 / free the segment-tree memory
    return ans;                             // 回傳答案陣列（呼叫端負責釋放）/ return the answer array (caller frees)
}