Anti-Rhyme Pairs

题目描述

PDF

通常两个押韵的单词也以相同的字符顺序结尾。我们用这个性质来定义反韵的概念。反韵词是一对开头相似的词。

同时定义一对字符串的反韵度为这两个字符串的最长公共前缀的长度

例如，arboreal和arcturus的反韵度是$2$，chalboard和overboard的反韵度是$0$。

给出一个单词列表和一个$(i, j)$形式的查询列表，输出由列表中的第$i$个单词和第$j$个单词组成的字符串对的反韵度。

输入格式

输入包含多组数据

第一行一个整数$T$表示样例数量，接下来几行共同描述一组数据。

每组数据第一行一个整数$N$表示单词个数

接下来$N$行，每行一个字符串表示单词列表中的一个单词，编号从$1$开始，保证只含小写字母

第$N+2$行一个整数$Q$表示查询的次数

接下来$Q$行，每行两个有空格分隔的整数$i, j$意义如题目所说

输出格式

输出包含$T$个分组 每个分组以Case X:开头，其中$X$表示数据组数，且从$1$开始计数 接下来$Q$行，每行包含一个整数，表示字符串对$(i, j)$的反韵度

数据范围

设字符串的长度为$L$ $T \leqslant 35,\;1 \leqslant N \leqslant 10^5,\;\;l \leqslant 10^4,\;N \times L \leqslant 10^6,\;1 \leqslant Q \leqslant 10^6,\;1 \leqslant i, j \leqslant N$