字符串匹配算法

字符串

KMP

• 模板(见博客)

AC自动机

• 模板(简单版)--判断模式串是否在文本串上出现了
  见yyb博客
  (但yyb的第一个做法是trie图,在有些题目中不可行(会TLE),第二个对了)
• 多提一句，若要统计模式串在文本串中的出现次数：
  1.
  在fail图(原trie树预处理后的)上的做法：
  在每个模式串结束的点挂一个链(如果保证串不重复,开个指针就行)指向该串的ans[]数组,每次扫到该点就ans[指向]++即可.复杂度可能被卡！！
• 模板(加强版)
  2.
  在fail树(沿着fail指针建的树(每个点只经过一次))上的做法：
  在树上(沿着fail指针建的树)跑一跑 复杂度线性
• cjoj例题
• My codes
• 洛谷 P2414 [NOI2011]阿狸的打字机