字符串 T = abcabaabcabac,字符串 P = abaa,判断P是否是T的子串,就是字符串匹配问题了,T 叫做文本(Text) ,P 叫做模式(Pattern),所以正确描述是,找出所有在文本 T = abcabaabcabac 中模式 P = abaa 的所有出现。
方法分为: 朴素算法,也叫做 BF(Brute-Force)算法
高级算法:Rabin-Karp算法,Knuth-Morris-Pratt算法,字典树,AC自动机。
模式匹配概述:http://mindlee.com/2011/11/25/string-matching/
KMP详解:https://zhuanlan.zhihu.com/p/24649304
正则表达式(概念讲的比较好): https://zhuanlan.zhihu.com/p/27338649
有限状态机无限状态机??? 还不太懂。。。。。
非确定型有穷自动机/确定型有穷自动机 NFA&DFA:https://zh.wikipedia.org/wiki/%E9%9D%9E%E7%A1%AE%E5%AE%9A%E6%9C%89%E9%99%90%E7%8A%B6%E6%80%81%E8%87%AA%E5%8A%A8%E6%9C%BA
正则语言: 同样不知所云。。。。。
https://zh.wikipedia.org/wiki/%E6%AD%A3%E5%88%99%E8%AF%AD%E8%A8%80
Hyperscan与PCRE比较: http://syswift.com/1.html
自动机:
http://blog.csdn.net/c601097836/article/details/47040703
https://baike.baidu.com/item/%E8%87%AA%E5%8A%A8%E6%9C%BA
https://zh.wikipedia.org/wiki/%E8%87%AA%E5%8B%95%E6%A9%9F%E7%90%86%E8%AB%96
一个用于状态机编译解析的库 Ragel http://www.colm.net/open-source/ragel/
Understanding the formal relationship between regular expressions and deterministic finite automata is key to using Ragel effectively.
理解正则表达式与确定有限状态自动机之间的关系,是用好这个库的关键。
AC, NFA, DFA有什么关系?
使用Aho-Corasick算法需要三步:
1.建立模式的Trie
2.给Trie添加失败路径
3.根据AC自动机,搜索待处理的文本
在第三步里,的AC自动机,可以使用NFA实现,或者DFA实现。
http://www.itwendao.com/article/detail/432004.html
PCRE:https://www.pcre.org/
perl: [knowledge][perl][pcre][sed] sed / PCRE 语法/正则表达式