基本概念
1、串的基本定义：
（1）串（string）（或字符串）是由零个或多个字符组成的有限序列，一般记为
s=‘a1a2···an’(n≥0)
其中，s是串的名，用单引号括起来的字符序列是串的值；ai(1≤i≤n)可以是字母、数字或其他字符；串中字符的数目n称为串的长度。零个字符的串称为空串（nullstring），它的长度为零。
（2）子串、主串、位置
串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。
例如：假设a、b、c、d为如下的4个串：
a=‘BEI’b=‘JING’
c=‘BEIJING’d=‘BEIJING’
则它们的长度分别是3、4、7和8；并且a和b都是c和d的子串，a在c和d中的位置都是1，而b在c中的位置是4，在d中的位置则是5。
（3）串相等
只有当两个串的长度相等，并且各个对应位置的字符都相等时才相等，称两个串是相等的。例如上例中的串a、b、c和d彼此都不相等。
2、串的模式匹配算法
（1）简单模式匹配
子串的定位操作通常称做串的模式匹配，是各种串处理系统的重要操作之一。
在简单模式匹配算法（也称为最朴素的匹配算法）中，分别利用计数指针i和j指示主串S和模式串P中当前正待比较的字符位置。算法的基本思想是：从主串S的第一个位置起和模式串的第一个字符比较之，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式串的字符比较之。依此类推，直至模式串P中的每个字符依次和主串S的一个连续的字符序列相等，则称匹配成功，否则称匹配不成功。
（2）KMP算法
KMP算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。其改进在于：每当一趟匹配过程中出现字符比较不等时，不需要回溯i指针，而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后，继续进行比较。
预告：明天会有KMP算法的真题演示及详细解析哟～既然和小编约定好了，那就不见不散啦！
更多考研福利