U530353 魔法古籍的解密之旅[没坑]

在一座被遗忘的远古遗迹中，发现了一本神秘的魔法古籍。古籍中记录了一系列的咒语，每个咒语由一串字符组成。然而，这些咒语并不完整，似乎~~缺失~~了某些关键的信息。 大魔法师阿尔萨斯研究发现，这些咒语可以通过某种方式在一篇远古魔法文本中找到线索。具体而言，古籍中的每个咒语可能出现在这篇远古魔法文本的不同位置，但某些咒语可能会彼此**重叠或者干扰**。 为了成功解读这些咒语，你需要找出所有咒语在魔法文本中出现的位置，并计算所有匹配的**总次数**。

给定一篇长度为 ????的魔法文本 ???? (仅包含小写字母 'a' - 'z')，以及M个咒语( 字符串集合 P1,P2...P(M) )你需要统计所有咒语在S中的匹配次数总和。每个咒语可能在文本中出现多次，且可能重叠。例如，在字符串 "ababab" 中，模式 "aba" 出现了**两次**(位置 0 和 2)。

第一行包含两个整数 n 和 m，分别表示文本的长度和模式串的个数。（1 ≤ n ≤ 100000，1 ≤ m ≤ 1000） 第二行包含一个长度为 n 的字符串 S，表示文本内容，仅包含**小写英文字母**。 接下来的 m 行，每行包含一个模式串 P_i（1 ≤ |P_i≤1000），仅包含小写英文字母。

一个整数，表示所有模式串在文本中出现的总次数（包括重叠匹配）。

暴力解法~~不可行~~(**可以试试**)！ 如果使用朴素字符串匹配，每个模式串搜索一遍主串，时间复杂度可能达到 O(N∑∣Pi∣)，这**远远**超出限制。 温馨提示 最低要求时间复杂度：O( N+∑∣Pi ) **数据范围已经给过 不再赘述**