LCP Queries
Source: aizu

LCP Queries
Problem Statement

A string $x$ is called a prefix of a string $y$ if $x$ can be obtained by repeating the removal of the last letter of $y$ zero or more times. For example, “abac”, “aba”, “ab”, “a”, and an empty string are the prefixes of “abac”.

For two strings $x$ and $y$, let $LCP(x, y)$ be the length of the longest common prefix of $x$ and $y$. For example, $LCP(“abacab”, “abacbba”) = 4$ because the longest common prefix of these two strings is “abac”. Note that $LCP(x, y)$ is always defined for any strings $x$ and $y$ because at least an empty string is one of their common prefixes.

You are given $n$ strings $s_1, ..., s_n$ and $m$ strings $t_1, ..., t_m$ of lowercase English letters. Then, you are given $q$ queries. In each query you are given an integer sequence $a_1, ..., a_k$. Let $u$ be the concatenation of $t_{a_1}, ..., t_{a_k}$. Your task is to calculate $\sum_{i=1}^n LCP(u, s_i)$.

Input

The input consists of a single test case of the following format.

$n$
$s_1$
$\vdots$
$s_n$
$m$
$t_1$
$\vdots$
$t_m$
$q$
$Query_1$
$\vdots$
$Query_q$


The first line consists of an integer $n$. Each of the next $n$ lines consists of a non-empty string $s_i$ of lowercase English letters. The next line consists of an integer $m$. Each of the next $m$ lines consists of a non-empty string $t_j$ of lowercase English letters.

The next line consists of an integer $q$. Then $q$ queries are given in order. Each of the queries is given in a single line in the following format.

$k$ $a_1$ ... $a_k$


$k$ is a positive integer which represents the length of the integer sequence of this query. Each $a_i$ is an integer between $1$ and $m$, inclusive.

You can assume that $1 \leq n \leq 200,000$, $1 \leq m \leq 200,000$ and $1 \leq q \leq 200,000$. The sum of lengths of $s_i$ does not exceed $200,000$. Similarly, the sum of lengths of $t_i$ does not exceed $200,000$. The sum of $k$ over all queries does not exceed $200,000$.

Output

Output $q$ lines. The $i$-th line should be the answer to the $i$-th query.

Sample Input
5
abcde
aaa
a
ab
bcd
5
a
bc
de
aaaa
b
5
1 1
3 1 2 3
2 2 3
5 5 4 3 2 1
3 3 3 3

Sample Output
4
9
3
1
0


C++ solution:
// AOJ #3619
// LCP Queries 2026.2.8

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using ll = long long;
 
static const ull BASE = 131ULL;
 
vector<ull> powerArr;
 
void precomputePowers(int n) {
    powerArr.resize(n+1);
    powerArr[0] = 1;
    for (int i = 1; i <= n; i++){
        powerArr[i] = powerArr[i-1] * BASE;
    }
}
 
struct TrieNode {
    int nxt[26];
    int parent;
    char letter;
    int count;
    int depth;
    int childCount;
    TrieNode(){
        memset(nxt, -1, sizeof(nxt));
        parent = -1;
        letter = 0;
        count = 0;
        depth = 0;
        childCount = 0;
    }
};
 
vector<TrieNode> trie;
 
void insertTrie(const string &s) {
    int cur = 0;
    trie[cur].count++;
    for (char c : s) {
        int idx = c - 'a';
        if(trie[cur].nxt[idx] == -1){
            trie[cur].nxt[idx] = trie.size();
            TrieNode newNode;
            newNode.parent = cur;
            newNode.letter = c;
            newNode.depth = trie[cur].depth + 1;
            trie.push_back(newNode);
            trie[cur].childCount++;
        }
        cur = trie[cur].nxt[idx];
        trie[cur].count++;
    }
}
 
vector<int> chainId;
vector<int> chainIndex;
 
struct ChainSegment {
    vector<int> nodes;
    vector<char> letters;
    vector<ll> ps;
    vector<ull> hashArr;
};
 
vector<ChainSegment> chains;
 
void assignChainSegment(int head) {
    int segId = chains.size();
    ChainSegment seg;
    int cur = head;
    int idx = 0;
    while (true) {
        chainId[cur] = segId;
        chainIndex[cur] = idx;
        seg.nodes.push_back(cur);
 
        if(trie[cur].childCount == 1) {
            int nextNode = -1;
            for (int c = 0; c < 26; c++){
                int child = trie[cur].nxt[c];
                if(child != -1){
                    if(nextNode == -1) nextNode = child;
                    else { nextNode = -2; break; }
                }
            }
            if(nextNode >= 0){
                cur = nextNode;
                idx++;
                continue;
            }
        }
        break;
    }
    int segSize = seg.nodes.size();
    if(segSize > 1) {
        seg.letters.resize(segSize - 1);
        for (int i = 1; i < segSize; i++){
            seg.letters[i-1] = trie[ seg.nodes[i] ].letter;
        }
    }
    seg.ps.resize(segSize);
    seg.ps[0] = 0;
    for (int i = 1; i < segSize; i++){
        seg.ps[i] = seg.ps[i-1] + trie[ seg.nodes[i] ].count;
    }
    seg.hashArr.resize(seg.letters.size() + 1);
    seg.hashArr[0] = 0;
    for (int i = 0; i < seg.letters.size(); i++){
        seg.hashArr[i+1] = seg.hashArr[i] * BASE + (ull)(seg.letters[i] - 'a' + 1);
    }
    chains.push_back(move(seg));
}
 
void dfsAssignChains(int v) {
    for (int c = 0; c < 26; c++){
        int child = trie[v].nxt[c];
        if(child == -1) continue;
        if(chainId[child] == -1) {
            if(v == 0 || trie[v].childCount != 1) {
                assignChainSegment(child);
            }
        }
        dfsAssignChains(child);
    }
}
 
void buildChainSegments() {
    int nNodes = trie.size();
    chainId.assign(nNodes, -1);
    chainIndex.assign(nNodes, -1);
    assignChainSegment(0);
    dfsAssignChains(0);
}
 
struct Tstring {
    string s;
    vector<ull> hashArr;
};
 
vector<Tstring> tStrings;
 
void computeHashForT(Tstring &ts) {
    int len = ts.s.size();
    ts.hashArr.resize(len+1);
    ts.hashArr[0] = 0;
    for (int i = 0; i < len; i++) {
        ts.hashArr[i+1] = ts.hashArr[i] * BASE + (ull)(ts.s[i]-'a'+1);
    }
}
 
 
inline ull getSubstringHash_T(const vector<ull> &tHash, int pos, int len) {
    return tHash[pos + len] - tHash[pos] * powerArr[len];
}
 
inline ull getSubstringHash_chain(const vector<ull> &chainHash, int pos, int len) {
    return chainHash[pos + len] - chainHash[pos] * powerArr[len];
}
 
 
int binarySearchMatch(const vector<ull> &tHash, int tPos, int limit, const vector<ull> &chainHash, int chainPos) {
    int low = 0, high = limit + 1;
    while(high - low > 1){
        int mid = (low + high) / 2;
        ull hashT = getSubstringHash_T(tHash, tPos, mid);
        ull hashChain = getSubstringHash_chain(chainHash, chainPos, mid);
        if(hashT == hashChain) low = mid;
        else high = mid;
    }
    return low;
}
 
ll simulateQuery(const vector<int> &tIndices) {
    ll ans = 0;
    int curNode = 0;
    for (int idx : tIndices) {
        if(curNode == -1) break;
        Tstring &ts = tStrings[idx];
        int tlen = ts.s.size();
        int pos = 0;
        while(pos < tlen && curNode != -1) {
            int cid = chainId[curNode];
            int cindex = chainIndex[curNode];
            ChainSegment &seg = chains[cid];
            int available = (int) seg.letters.size() - cindex;
            int remaining = tlen - pos;
 
            if(available > 0){
                int jumpLimit = min(available, remaining);
                int Lmatch = binarySearchMatch(ts.hashArr, pos, jumpLimit, seg.hashArr, cindex);
                if(Lmatch > 0){
                    ans += seg.ps[cindex + Lmatch] - seg.ps[cindex];
                    curNode = seg.nodes[cindex + Lmatch];
                    pos += Lmatch;
                    continue;
                }
            }
            char c = ts.s[pos];
            int letterIndex = c - 'a';
            if(trie[curNode].nxt[letterIndex] == -1) {
                curNode = -1;
                break;
            } else {
                curNode = trie[curNode].nxt[letterIndex];
                ans += trie[curNode].count;
                pos++;
            }
        }
        if(curNode == -1) break;
    }
    return ans;
}
 
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int n;
    cin >> n;
    trie.reserve(210000);
    trie.push_back(TrieNode());
 
    string s;
    for (int i = 0; i < n; i++){
        cin >> s;
        insertTrie(s);
    }
 
    buildChainSegments();
 
    precomputePowers(210000);
 
    int m;
    cin >> m;
    tStrings.resize(m);
    for (int i = 0; i < m; i++){
        cin >> s;
        tStrings[i].s = s;
        computeHashForT(tStrings[i]);
    }
 
    int q;
    cin >> q;
    for (int qi = 0; qi < q; qi++) {
        int k;
        cin >> k;
        vector<int> indices(k);
        for (int i = 0; i < k; i++){
            int tmp;
            cin >> tmp;
            indices[i] = tmp - 1;
        }
        ll answer = simulateQuery(indices);
        cout << answer << endl;
    }
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

type TrieNode struct {
	children [26]*TrieNode
	count    int
}

func insertTrie(root *TrieNode, s string) {
	node := root
	for _, c := range s {
		idx := c - 'a'
		if node.children[idx] == nil {
			node.children[idx] = &TrieNode{}
		}
		node = node.children[idx]
		node.count++
	}
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	scanner.Scan()
	n, _ := strconv.Atoi(scanner.Text())

	root := &TrieNode{}
	for i := 0; i < n; i++ {
		scanner.Scan()
		s := scanner.Text()
		insertTrie(root, s)
	}

	scanner.Scan()
	m, _ := strconv.Atoi(scanner.Text())
	tStrings := make([]string, m)
	for i := 0; i < m; i++ {
		scanner.Scan()
		tStrings[i] = scanner.Text()
	}

	scanner.Scan()
	q, _ := strconv.Atoi(scanner.Text())
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	for qi := 0; qi < q; qi++ {
		scanner.Scan()
		k, _ := strconv.Atoi(scanner.Text())
		indices := make([]int, k)
		for i := 0; i < k; i++ {
			scanner.Scan()
			tmp, _ := strconv.Atoi(scanner.Text())
			indices[i] = tmp - 1
		}

		var sumLCP int
		node := root
		for _, idx := range indices {
			s := tStrings[idx]
			for _, c := range s {
				idx := c - 'a'
				if node.children[idx] == nil {
					goto nextQuery
				}
				node = node.children[idx]
				sumLCP += node.count
			}
		}
	nextQuery:
		fmt.Fprintln(writer, sumLCP)
	}
}

Java solution:
import java.io.*;
import java.util.*;

public class Main {
    static final long BASE = 131;
    static long[] powerArr;

    static class TrieNode {
        int[] next = new int[26];
        int parent = -1;
        char letter;
        int count = 0;
        int depth = 0;
        int childCount = 0;

        TrieNode() {
            Arrays.fill(next, -1);
        }
    }

    static List<TrieNode> trie = new ArrayList<>();
    static int[] chainId;
    static int[] chainIndex;

    static class ChainSegment {
        List<Integer> nodes = new ArrayList<>();
        List<Character> letters = new ArrayList<>();
        long[] prefixSum;
        long[] hashArr;
    }

    static List<ChainSegment> chains = new ArrayList<>();

    static void insertTrie(String s) {
        int cur = 0;
        trie.get(cur).count++;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int idx = c - 'a';
            if (trie.get(cur).next[idx] == -1) {
                trie.get(cur).next[idx] = trie.size();
                TrieNode newNode = new TrieNode();
                newNode.parent = cur;
                newNode.letter = c;
                newNode.depth = trie.get(cur).depth + 1;
                trie.add(newNode);
                trie.get(cur).childCount++;
            }
            cur = trie.get(cur).next[idx];
            trie.get(cur).count++;
        }
    }

    static void assignChainSegment(int head) {
        int segId = chains.size();
        ChainSegment seg = new ChainSegment();
        int cur = head;
        int idx = 0;
        while (true) {
            chainId[cur] = segId;
            chainIndex[cur] = idx;
            seg.nodes.add(cur);

            if (trie.get(cur).childCount == 1) {
                int nextNode = -1;
                for (int c = 0; c < 26; c++) {
                    int child = trie.get(cur).next[c];
                    if (child != -1) {
                        if (nextNode == -1) {
                            nextNode = child;
                        } else {
                            nextNode = -2;
                            break;
                        }
                    }
                }
                if (nextNode >= 0) {
                    cur = nextNode;
                    idx++;
                    continue;
                }
            }
            break;
        }
        int segSize = seg.nodes.size();
        if (segSize > 1) {
            for (int i = 1; i < segSize; i++) {
                seg.letters.add(trie.get(seg.nodes.get(i)).letter);
            }
        }
        seg.prefixSum = new long[segSize];
        seg.prefixSum[0] = 0;
        for (int i = 1; i < segSize; i++) {
            seg.prefixSum[i] = seg.prefixSum[i - 1] + trie.get(seg.nodes.get(i)).count;
        }
        seg.hashArr = new long[seg.letters.size() + 1];
        seg.hashArr[0] = 0;
        for (int i = 0; i < seg.letters.size(); i++) {
            seg.hashArr[i + 1] = seg.hashArr[i] * BASE + (seg.letters.get(i) - 'a' + 1);
        }
        chains.add(seg);
    }

    static void dfsAssignChains(int v) {
        for (int c = 0; c < 26; c++) {
            int child = trie.get(v).next[c];
            if (child == -1) continue;
            if (chainId[child] == -1) {
                if (v == 0 || trie.get(v).childCount != 1) {
                    assignChainSegment(child);
                }
            }
            dfsAssignChains(child);
        }
    }

    static void buildChainSegments() {
        int nNodes = trie.size();
        chainId = new int[nNodes];
        chainIndex = new int[nNodes];
        Arrays.fill(chainId, -1);
        Arrays.fill(chainIndex, -1);
        assignChainSegment(0);
        dfsAssignChains(0);
    }

    static class TString {
        String s;
        long[] hashArr;

        void computeHash() {
            int len = s.length();
            hashArr = new long[len + 1];
            hashArr[0] = 0;
            for (int i = 0; i < len; i++) {
                hashArr[i + 1] = hashArr[i] * BASE + (s.charAt(i) - 'a' + 1);
            }
        }
    }

    static long getSubstringHashT(long[] hashArr, int pos, int len) {
        return hashArr[pos + len] - hashArr[pos] * powerArr[len];
    }

    static long getSubstringHashChain(long[] hashArr, int pos, int len) {
        return hashArr[pos + len] - hashArr[pos] * powerArr[len];
    }

    static int binarySearchMatch(long[] tHash, int tPos, int limit, long[] chainHash, int chainPos) {
        int low = 0, high = limit + 1;
        while (high - low > 1) {
            int mid = (low + high) / 2;
            long hashT = getSubstringHashT(tHash, tPos, mid);
            long hashChain = getSubstringHashChain(chainHash, chainPos, mid);
            if (hashT == hashChain) {
                low = mid;
            } else {
                high = mid;
            }
        }
        return low;
    }

    static long simulateQuery(List<Integer> tIndices, List<TString> tStrings) {
        long ans = 0;
        int curNode = 0;
        for (int idx : tIndices) {
            if (curNode == -1) break;
            TString ts = tStrings.get(idx);
            int tlen = ts.s.length();
            int pos = 0;
            while (pos < tlen && curNode != -1) {
                int cid = chainId[curNode];
                int cindex = chainIndex[curNode];
                ChainSegment seg = chains.get(cid);
                int available = seg.letters.size() - cindex;
                int remaining = tlen - pos;

                if (available > 0) {
                    int jumpLimit = Math.min(available, remaining);
                    int Lmatch = binarySearchMatch(ts.hashArr, pos, jumpLimit, seg.hashArr, cindex);
                    if (Lmatch > 0) {
                        ans += seg.prefixSum[cindex + Lmatch] - seg.prefixSum[cindex];
                        curNode = seg.nodes.get(cindex + Lmatch);
                        pos += Lmatch;
                        continue;
                    }
                }
                char c = ts.s.charAt(pos);
                int letterIndex = c - 'a';
                if (trie.get(curNode).next[letterIndex] == -1) {
                    curNode = -1;
                    break;
                } else {
                    curNode = trie.get(curNode).next[letterIndex];
                    ans += trie.get(curNode).count;
                    pos++;
                }
            }
            if (curNode == -1) break;
        }
        return ans;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // Precompute powers of BASE
        powerArr = new long[210000];
        powerArr[0] = 1;
        for (int i = 1; i < 210000; i++) {
            powerArr[i] = powerArr[i - 1] * BASE;
        }

        // Initialize trie with root node
        trie.add(new TrieNode());

        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            insertTrie(s);
        }

        buildChainSegments();

        int m = Integer.parseInt(br.readLine());
        List<TString> tStrings = new ArrayList<>(m);
        for (int i = 0; i < m; i++) {
            TString ts = new TString();
            ts.s = br.readLine();
            ts.computeHash();
            tStrings.add(ts);
        }

        int q = Integer.parseInt(br.readLine());
        for (int qi = 0; qi < q; qi++) {
            String[] parts = br.readLine().split(" ");
            int k = Integer.parseInt(parts[0]);
            List<Integer> indices = new ArrayList<>(k);
            for (int i = 1; i <= k; i++) {
                indices.add(Integer.parseInt(parts[i]) - 1);
            }
            long answer = simulateQuery(indices, tStrings);
            bw.write(answer + "\n");
        }
        bw.flush();
    }
}

JavaScript solution:
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal: false
});

async function main() {
    let n, m, q;
    let s = [];
    let t = [];
    let queries = [];
    let lineNumber = 0;

    for await (const line of rl) {
        if (lineNumber === 0) {
            n = parseInt(line);
        } else if (lineNumber <= n) {
            s.push(line.trim());
        } else if (lineNumber === n + 1) {
            m = parseInt(line);
        } else if (lineNumber <= n + m + 1) {
            t.push(line.trim());
        } else if (lineNumber === n + m + 2) {
            q = parseInt(line);
        } else {
            const parts = line.trim().split(/\s+/);
            const k = parseInt(parts[0]);
            const indices = parts.slice(1).map(x => parseInt(x) - 1);
            queries.push(indices);
        }
        lineNumber++;
    }

    for (const query of queries) {
        let u = '';
        for (const idx of query) {
            u += t[idx];
        }
        let total = 0;
        for (const str of s) {
            let lcp = 0;
            const minLen = Math.min(str.length, u.length);
            while (lcp < minLen && str[lcp] === u[lcp]) {
                lcp++;
            }
            total += lcp;
        }
        console.log(total);
    }
}

main().catch(err => {
    console.error(err);
    process.exit(1);
});

Python solution:
import sys
from sys import stdin
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    ptr = 0

    n = int(input[ptr])
    ptr += 1
    s_list = []
    for _ in range(n):
        s = input[ptr]
        ptr += 1
        s_list.append(s)

    # Trie construction
    trie = [{}]
    count = [0]

    for s in s_list:
        node = 0
        count[node] += 1
        for c in s:
            if c not in trie[node]:
                trie[node][c] = len(trie)
                trie.append({})
                count.append(0)
            node = trie[node][c]
            count[node] += 1

    m = int(input[ptr])
    ptr += 1
    t_strings = []
    for _ in range(m):
        t = input[ptr]
        ptr += 1
        t_strings.append(t)

    q = int(input[ptr])
    ptr += 1
    output = []
    for _ in range(q):
        k = int(input[ptr])
        ptr += 1
        indices = list(map(int, input[ptr:ptr + k]))
        ptr += k
        t_indices = [idx - 1 for idx in indices]
        # Concatenate the t strings (logically)
        concatenated_t = ''.join([t_strings[ti] for ti in t_indices])
        # Compute the sum of LCPs with all s strings
        total = 0
        for s in s_list:
            lcp = 0
            min_len = min(len(s), len(concatenated_t))
            while lcp < min_len and s[lcp] == concatenated_t[lcp]:
                lcp += 1
            total += lcp
        output.append(str(total))
    print('\n'.join(output))

if __name__ == '__main__':
    main()

Ruby solution:
require 'stringio'

BASE = 131
MOD = 10**18 + 3

def precompute_powers(max_len)
  power = Array.new(max_len + 1, 1)
  (1..max_len).each do |i|
    power[i] = (power[i-1] * BASE) % MOD
  end
  power
end

def compute_hash(s)
  hash_arr = Array.new(s.size + 1, 0)
  (0...s.size).each do |i|
    hash_arr[i+1] = (hash_arr[i] * BASE + s[i].ord) % MOD
  end
  hash_arr
end

def get_substring_hash(hash_arr, pos, len, powers)
  (hash_arr[pos + len] - hash_arr[pos] * powers[len] % MOD + MOD) % MOD
end

def main
  input = StringIO.new(ARGF.read)
  n = input.gets.to_i
  s_strings = []
  s_hashes = []
  n.times do
    s = input.gets.chomp
    s_strings << s
    s_hashes << compute_hash(s)
  end

  m = input.gets.to_i
  t_strings = []
  m.times do
    t_strings << input.gets.chomp
  end

  powers = precompute_powers(200000)

  q = input.gets.to_i
  q.times do
    parts = input.gets.split.map(&:to_i)
    k = parts[0]
    indices = parts[1..k].map { |x| x - 1 }
    u = indices.map { |idx| t_strings[idx] }.join
    u_hash = compute_hash(u)

    total = 0
    s_strings.each_with_index do |s, i|
      s_len = s.size
      u_len = u.size
      max_possible = [s_len, u_len].min
      lcp = 0
      (1..max_possible).each do |len|
        s_hash = get_substring_hash(s_hashes[i], 0, len, powers)
        u_hash_segment = get_substring_hash(u_hash, 0, len, powers)
        if s_hash == u_hash_segment
          lcp = len
        else
          break
        end
      end
      total += lcp
    end
    puts total
  end
end

main