对于这题,看到字符串匹配,第一反应想到字符串hash,同时看到$len \leq 8 $ ,考虑对于先给出的$n$个字符串,$O(len^2)$枚举它的子串,将其加入$map$中,但是要注意如果一个然后对于每个字符串,我们都统计一下它最后一次出现在哪里(于是就可以顺便判一下重)

然后我们在询问的时候,就可以直接输出这个字符串对应的出现次数以及最后一处出现的位置啦QwQ

STL大法好!

(看到楼下的大佬们都没有用我这个方法,我就来脱碳甲醛一下辣~~)


以上都是废话

我所说的这个方法,具体思路是这样的:

  • 最首先,基础的并查集大家应该都会,如果不会的话可以看代码或者出门右转P3367并查集模板
  • 然后,STL中的Map可以直接方便地解决字符串哈希的问题
  • 但是,每次都用一遍Map似乎显得有些不优美,似乎有些慢的说
  • 所以,我们需要引进两个数组,一个Num和一个Names
  • Num是一个Map,它的作用就是Num[“A”]表示名为A的人的编号
  • 于是,Names就是反过来的Num,Name[i]表示编号为i的人的名字
  • 总体而言,不仅加快了速度,还方便了调试