|
|
|
子串的定位操作通常称为串的模式匹配，它是各种串处理系统中最重要的运算之一。子串也称为模式串。
|
|
|
|
|
|
朴素的模式匹配算法也称为布鲁特一福斯算法，其基本思想是：从主串的第一个字符起与模式串的第一个字符比较，若相等则继续逐个字符进行后续的比较，否则从主串的第二个字符起与模式串的第一个字符重新比较，直至模式串中的每个字符依次和主串中的一个连续的字符序列相等，则称匹配成功，否则称匹配失败。
|
|
|
|
该算法在最好情况下匹配算法的时间复杂度为O(n+m)，而在最坏情况下的时间复杂度为O(n×m)。
|
|
|
|
|
|
改进的模式匹配算法又称为KMP算法，其改进之处在于：每当匹配过程中出现相比较的字符不相等时，不需要回溯主串的指针，而是利用已经得到的"部分匹配"的结果，将模式串向后"滑动"尽可能远的距离，再继续进行比较。
|
|
|
|
|
