struct Tree int index childs26; rever1500000 order1500000;class Solution private int reverCnt = 0 orderCnt = 0;public void insertconst string& word const int& index int p1 = 0 p2 = 0

interface Tree { index: number; childs: number[]; } let rever: Tree[] = new Array(1500000); let order: Tree[] = new Array(1500000);

class Solution { private reverCnt: number = 0; private orderCnt: number = 0;

private insert(word: string, index: number): void {
    let p1: number = 0;
    let p2: number = 0;
    let ch: number = 0;
    let n: number = word.length;
    for (let i = 0; i < n; ++i) {
        ch = word.charCodeAt(i) - 'a'.charCodeAt(0);
        if (!order[p1].childs[ch]) {
            order[p1].childs[ch] = ++this.orderCnt;
        }
        p1 = order[p1].childs[ch];

        ch = word.charCodeAt(n - 1 - i) - 'a'.charCodeAt(0);
        if (!rever[p2].childs[ch]) {
            rever[p2].childs[ch] = ++this.reverCnt;
        }
        p2 = rever[p2].childs[ch];
    }
    order[p1].index = rever[p2].index = index;
}

private isPalindrome(word: string, i: number, j: number): boolean {
    while (i < j) {
        if (word[i++] !== word[j--]) return false;
    }
    return true;
}

private searchRever(word: string, index: number, ret: number[][]): void {
    let p: number = 0;
    for (let i = 0; i < word.length; ++i) {
        let j: number = word.charCodeAt(i) - 'a'.charCodeAt(0);
        if (rever[p].index && this.isPalindrome(word, i, word.length - 1)) {
            ret.push([index - 1, rever[p].index - 1]);
        }
        if (!rever[p].childs[j]) {
            return;
        }
        p = rever[p].childs[j];
    }
    if (rever[p].index && rever[p].index !== index) {
        ret.push([index - 1, rever[p].index - 1]);
    }
}

private searchOrder(word: string, index: number, ret: number[][]): void {
    let p: number = 0;
    for (let i = word.length - 1; i >= 0; --i) {
        let j: number = word.charCodeAt(i) - 'a'.charCodeAt(0);
        if (order[p].index && this.isPalindrome(word, 0, i)) {
            ret.push([order[p].index - 1, index - 1]);
        }
        if (!order[p].childs[j]) {
            return;
        }
        p = order[p].childs[j];
    }
}

public palindromePairs(words: string[]): number[][] {
    for (let i = 0; i < words.length; ++i) {
        this.insert(words[i], i + 1);
    }
    let ret: number[][] = [];
    for (let i = 0; i < words.length; ++i) {
        this.searchRever(words[i], i + 1, ret);
        this.searchOrder(words[i], i + 1, ret);
    }
    rever = new Array(1500000);
    order = new Array(1500000);
    return ret;
}