注意到有一个条件 Σ|t[i]|<5e5
记L=sqrt(Σ|t[i]|)
把长度大于L的串叫做长串,这种串至多只有L个
对于这种串,我们可以s拼起来 对 t+"#"+s求z函数,然后扫一次,把答案累加起来 复杂度是 n*L的
把长度小于L的串叫做短串
对于这种串,我们全部存到trie中,然后扫一次s的每个后缀,暴力匹配,因为所有存入trie中的字符串至多只有L长
所以trie的高度至多只有L,提前break 复杂度就是 n*L 的
def zAlgo(string): n = len(string) z = [0] * n left, right = 0, 0 for i in range(1, n): z[i] = max(min(z[i - left], right - i + 1), 0) while i + z[i] < n and string[z[i]] == string[i + z[i]]: left, right = i, i + z[i] z[i] += 1 return z for _ in range(int(input())): n,m=map(int,input().split()) s=input() t=[] tl=0 for _ in range(m): x=input() tl+=len(x) t.append(x) sq=int(tl**0.5)+1 trie={} res=[0]*n for x in t: if len(x)>=sq: z=zAlgo(x+"#"+s) for i in range(len(x)+1,len(x)+1+len(s)): res[i-len(x)-1]+=z[i] else: cur=trie for i in x: if i not in cur: cur[i]={} cur=cur[i] if "#" not in cur: cur["#"]=0 cur["#"]+=1 for i in range(n): cur=trie for j in s[i:]: if j in cur: cur=cur[j] else: break res[i]+=cur.get("#",0) print(max(res))