字符串匹配的匹配种类
柔性字符串匹配
1974年Fischer和Paterson将通配符don't cares引入模式匹配问题 ，之后模式匹配的定义出现了各种各样非标准形式：按匹配方式分，有容错的近似匹配，交换相邻字母的交换匹配，服务于程序代码查错的参数匹配等；按匹配对象分，T、P可以是一张二维表，也可以分别含有通配符；按匹配结果分，有返回匹配位置和匹配数两种定义。Muthukrishna等人将上述各类问题统称为Non-standard Stringology 。然而，通配符的引入会让问题定义更加灵活，却也带来了复杂性。算法的设计有时不仅仅考虑时空效率，保证匹配结果的完备性很可能成为算法设计更重要的问题。甚至其中的某些问题被猜测具有NP难度。
带有通配符的串匹配
在Fischer和Paterson于1974年将通配符*引入模式匹配问题之后，如何将通配符与传统的模式匹配有效结合是研究的重点。这其中，最具代表性的定义是通配符指代的字符数不仅仅用一个固定的常数表示，而是一个可由用户自定义的区间 ，即带有上下限约束，如TCT*(30,50)TATA。 将上述带有区间的通配符扩展至任意两两相邻的字符之间，然而所有的通配符上下限相同，如A*(1,3)C*(1,3)G*(1,3)C。为了进一步放宽约束， 提出了不同通配符彼此独立的思想，如A*(0,3)C*(2,4)G*(1,1)C。 序列模式挖掘是数据挖掘的一个重要分支，是基于时间或者其他序列的经常发生的模式。序列模式的一个例子就是“一个9个月前买了一台PC的顾客有可能在一个月内买一个新的CPU”。很多数据都是这种时间序列形式的，我们就可以用它来市场趋势分析，客户保留和天气预测等等。序列模式首先是由R.Agrawal和R.Srikant提出的，随后几年研究者所提出的算法都是基于Apriori原理的改进算法。随后Zaki等人提出了基于垂直数据表示的SPADE算法。Han等提出了不产生候选集的基于模式增长的FP-Growth算法。接着Han等又研究出了基于投影数据库的FreeSpan和PrefixSpan算法。
