假期连载之八
本篇为连载七未完成内容的后续补充部分。我们继续讨论关于字符串的一些问题，最后将对STL中关于String的部分进行一些说明。
字符串的模式匹配
字符串的模式匹配问题描述如下：设有两个字符串pat和T，若打算在串T中查找是否有与串pat相等的字串，则称串T为目标Target，pat为模式Pattern，并称查找模式串在目标串中位置的运算成为模式匹配Pattern Matching。
1、 朴素（简单）的模式匹配
这种被称为B-F的模式匹配算法是由Brute和Force共同提出的一种基于简单穷举算法。该算法的思想是用pat的字符依次与T中的字符做比较，如果对应元素均相同，则匹配成功，返回模式串第0个字符P0在目标串T中的位置；如果其中某个位置i中有Ti！=Pi，则比较不等，此时将模式串pat右移一位，并用pat中的字符从头开始与T中的字符依次比较，反复执行上述过程，直到出现下列两种情况之一时结束算法：
执行过程中发现存在与模式串匹配的目标串子串，即匹配成功；
当模式串已经移到最后可能与T比较的位置，但并不能保证每个字符均可与T匹配，此时匹配失败，返回-1；
下面给出B-F算法的C++描述：
int Find(Astring& pat,int k) const
{ //Astring是默认定义的一个String类，k为在目标串中开始匹配的位置，const声明为常成员函数，这里有两重意义：首先常成员函数不能修改数据成员，也不能调用非const成员；其次在被声明为const的常对象中只能调用常成员函数。
int i,j;
for(i=k;i<=curLength-pat.Length;i++)
{//利用到了回溯的方法进行逐次匹配
for(j=0;j<pat.Length;j++)
if(ch[i+j]!=pat.ch[j])
break;
if(j==pat.Length)
return i;
}
return -1;
}
由上述算法可知，在最坏情况下，算法最多将比较n-m+1次，假设模式串长度远小于目标串，则算法运行时间为O(n*m)。
2、模式匹配的改进算法
为了改进B-F算法的性能，需消除其自带的回溯因素，因此需要对串本身进行进一步分析。
D.E.Knuth、J.H.Mprris和V.R.Pratt同时提出了基于简单模式匹配的改进算法—KMP算法，这种算法大大降低了字符串模式匹配算法的时间复杂度。
KMP算法本身可使用详细的图表进行说明，限于篇幅原因本文仅提供文字叙述，由于KMP算法的普遍性，众多文献均有丰富讲解，有兴趣的读者可以额外查阅。
在简单模式匹配中我们发现，由于P串一旦与T串发生“失配”，则无条件直接回溯至T串的k+1个位置重新匹配，其中浪费了很多P串内部规律的资源。理由如下：假设我们在Pj处发现“失配”，此时并不求助于T串，而是寻求一个非负整数k<j-1，使得P0…Pk=Pj-k-1…pj-1，由于P0…Pk肯定和T串对应于Pj-k-1…Pj-1的元素一一对应且相等，则将模式串第k位与目标串失配位置对齐，并从模式串的第k位开始比较即可。如果不能找到k值，则将模式串第0位与目标串失配位置对齐，并从模式串的第0位开始比较。
为了易于编程，一般我们先计算出P串对j=0,1,2,…,n的所有k值，据此求出下一次匹配模式串中与目标串上次失配位置对齐的相应位置。此距离使用数组next[]表示，我们先给出其数学规律：
-1， 当j=0;
next[j]={k+1， 当0<=k<j-1且使得P0P1…Pk=Pj-k-1…Pj-1的最大整数;
0， 其他所有情况;
j=0的情况，即模式串的第0位元素与目标串位置失配，此时将第0位与目标串失配位置的下一位置对齐即可。
例如对于字符串P=”abaabcac”，有next[]如下：
j 0 1 2 3 4 5 6 7
P a b a a b c a c
next(j) -1 0 0 1 1 2 0 1
我们对其中j=2、j=5的情况进行简短分析。当j=2时，得知k可能为0，当k=0时，有P0!=P1，因此k不存在，next(2)=0；当j=5时，k可能在0-3之间，由大到小比较，P0…P3!=P1…P4，故k!=3，P0P1P2!=P2P3P4，故k!=2，有P0P1=P3P4，故k=1，因此next(5)=k+1=2。
据此我们给出计算next[]的一般方法：
getNext(int next[])
{
int j=0,k=-1,lengthP=curLength; //curLength为模式串长度
next[0]=-1;
while(j<lengthP)
{
if(k==-1||ch[j]==ch[k])
{
j++;
k++;
next[j]=k;
}
else
k=next[k];
}
}
在求出next[]后，我们可以根据以下KMP算法实现快速匹配：
int fastFind(Astring& pat,int k,int next[])const
{ //此程序段的有关疑问请参考B-F程序段
int posP=0,posT=k;
int lengthP=pat.curLength;
int length=curLength;
while(posP<lengthP&&posT<lengthT)
{
if(posP==-1||pat.ch[posP]==ch[posT])
{
posP++;
posT++;
}
else
posP=next[posP];
}
if(posP<lengthP)
return -1;
else
return posT-lengthP;
}
易知整个算法的时间复杂度为O(lengthP+lengthT)。
字符串的模式匹配是一个应用极其广泛、重要的一种计算机算法问题。在普通的文本编辑器中随处可见模式匹配的功能用例，在目前流行的各种信息检索中模式匹配算法也是核心研究之一。数十年来不断有科研人员在寻找更加智能、更加高效的算法中取得成果，并不断产生革新。
在实际应用中，我们并不一定必须自己定义原始的模式匹配算法。例如正则表达式Regular Expression，就是一种建立在元字符基础上描述文本规则的强大工具。目前正则表达式被制作成了众多库，广泛支持各种高级语言，许多主流高级语言也已经内嵌了正则表达式。
STL String
STL中对于String的操作有了进一步规范，其在运算符重载、串查找函数的实现方面均有很大提高。以下为STL String中所定义的函数列表：
begin 得到指向字符串开头的Iterator
end 得到指向字符串结尾的Iterator
rbegin 得到指向反向字符串开头的Iterator
rend 得到指向反向字符串结尾的Iterator
size 得到字符串的大小
length 和size函数功能相同
max_size 字符串可能的最大大小
capacity 在不重新分配内存的情况下，字符串可能的大小
empty 判断是否为空
operator[] 取第几个元素，相当于数组
c_str 取得C风格的const char* 字符串
data 取得字符串内容地址
operator= 赋值操作符
reserve 预留空间
swap 交换函数
insert 插入字符
append 追加字符
push_back 追加字符
operator+= += 操作符
erase 删除字符串
clear 清空字符容器中所有内容
resize 重新分配空间
assign 和赋值操作符一样
replace 替代
copy 字符串到空间
find 查找
rfind 反向查找
find_first_of 查找包含子串中的任何字符，返回第一个位置
find_first_not_of 查找不包含子串中的任何字符，返回第一个位置
find_last_of 查找包含子串中的任何字符，返回最后一个位置
find_last_not_of 查找不包含子串中的任何字符，返回最后一个位置
substr 得到字串
compare 比较字符串
operator+ 字符串链接
operator== 判断是否相等
operator!= 判断是否不等于
operator< 判断是否小于
operator>> 从输入流中读入字符串
operator<< 字符串写入输出流
getline 从输入流中读入一行
由于多数读者从C开始接触到一些字符串操作的库函数，因此在学习C++后对同类型的部分容易发生混淆，唯一的办法只能是多实践，并经常总结相关内容，才能逐步熟练掌握。
（未完待续）