P12871 [蓝桥杯 2025 国 Python A] 倒排索引

在信息检索系统中，倒排索引是一种常用的数据结构，用于快速查找包含特定词语的文档集合。为了增强搜索的灵活性，我们引入了 N-Gram 分词算法，参数 $[\min, \max]$，表示分别按照长度 $\min$、$\min+1$、$\cdots$、$\max$ 对单词进行滑动窗口截取。例如对于 $[3, 5]$ 的 N-Gram，会将单词 $\tt{lanqb}$ 分割为 $[\tt{lan, anq, nqb, lanq, anqb, lanqb}]$ 的索引序列，如果文档长度小于 $\min$，那么索引序列只包含文档本身。 给定 $n$ 个文档，对于第 $i$ 个文档 $d_i$，利用上述的 N-Gram 算法为其生成一组索引序列 $L_i$。对于查询词 $q$，也对其应用 N-Gram 为其生成一个索引序列 $P$，如果序列 $P$ 中的某个单词出现在序列 $L_i$ 中，那么就认为查询词和文档 $d_i$ 匹配成功。 请统计查询词 $q$ 能与多少个文档匹配成功。

输入的第一行包含三个正整数 $n$，$\min$，$\max$，相邻整数之间使用一个空格分隔。 接下来 $n$ 行，每行包含一个字符串，其中第 $i$ 行的字符串表示文档 $d_i$。 接下来一行包含一个字符串，表示查询词 $q$。

输出一行包含一个整数表示答案。

**【样例说明】** 文档分词结果如下： - $\tt{angel}$：$[\tt{ang, nge, gel, ange, ngel}]$ - $\tt{ac}$：$[\tt{ac}]$ - $\tt{angle}$：$[\tt{ang, ngl, gle, angl, ngle}]$ 查询词分词结果如下： - $\tt{lang}$：$[\tt{lan, ang, lang}]$ $\tt{angel}$ 和 $\tt{angle}$ 的分词中都包含 $\tt{ang}$，所以答案为 $2$。 **【评测用例规模与约定】** 设 $|s|$ 表示字符串 $s$ 的长度。 对于 50% 的评测用例，$1 \leq n \leq 100$； 对于所有评测用例，$1 \leq n \leq 10^3$，$1 \leq \min \leq \max \leq 20$，$1 \leq |d_i|, |q| \leq 20$，$d_i$ 和 $q$ 都只包含小写英文字母。