我反思了一下前两篇的问题，发现讲知识点还是要简明扼要
常见的字符串里的名词
空串：不含任何字符的串，串长度=0
空格串：仅由一个或多个空格组成的串
子串：由串中任意个连续的字符组成的子序列。
主串：包含子串的串。 如：A=’Shenzhen University’ B=’University’ A为主串，B为子串
位置：字符在主串中的序号。子串在主串中的位置以子串第一个字符在主串中的位置来表示。
串相等的条件：当两个串的长度相等且各个对应位置的字符都相等时才相等。
模式匹配：确定子串在主串中首次出现的位置的运算
在串的基本操作中，通常以“串的整体”作为操作对象，如：在串中查找某个子串、在串的某个位置上插入一个子串等。很少以字符为操作单位（否则和线性表没有区别）
最小操作集：
这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除ClearString和串销毁DestroyString外）可在这个最小操作子集上实现。
怎么理解这个最小操作集？
例如判断串是否为空串的函数和判断串的字符个数（长度）的函数其实可以用同一个函数经过略微修改实现，比如我只需求串长，当长度=0即为空，本质上这两个函数都是求串长，则求串长是这两个操作的最小操作。
右边五种是#include<cstring>中已有的函数。左边五种是我们自己编写的函数，有这十个函数我们可以完成串的操作。
这是字符串的静态表示
而关于字符串的动态表示
首先是堆的概念 。
关于查找子串
int Index(SString S, SString T, int pos) {
// 返回子串T在主串S中第pos个字符之后的位置。若不存在，
// 则函数值为-1。其中，T非空，0≤pos≤S.length-1)。
i = pos; j = 0;
while (i <= s.length-1 && j <= t.length-1) {
if (S.ch[i] == T.ch[j]) { ++i; ++j; } // 继续比较后继字符
else { i = i-j+1; j = 0; } // 指针后退重新开始匹配
}
if (j ==t.length) return i-t.length;
else return -1;
} // Index` 朴素算法，优点是简单直接，缺点是时间复杂度高【最少m+n，最多m*n】
改进算法：KMP算法 —— 解决掉朴素算法的冗余比较
前置：next数组
什么是next数组？怎么求？我们另开一文来讲。机考复习我们直接上程序
本质上，next数组有两个版本，有模式串从j==1开始的，也有从j==0开始的，以上是从1开始，从零开始只需要将上述结果都-1即可。
求好了next数组，我们得以真正书写KMP算法，在上KMP算法之前，请看朴素算法，两者对比学习：
#include<iostream>
#include<string>
using namespace std;
//从pos位置开始，返回子串在主串中的位置
int BF(string M,string T,int pos)
{
int i=pos;
int j=0;
int Mlen=M.length();//主串的范围[0,Slen)
int Tlen=T.length();//子串的范围[0,Tlen)
if(pos<0 && pos>Mlen)
return -1;
while(i<Mlen && j<Tlen)
{
if(M[i]==T[j])
{
++i;
++j;
}
else
{
i=i-j+1;
j=0;
}
}
if(j>=Tlen)
return i-Tlen;
else
return -1;
}
int main()
{
string M="abcdefabcdx";
string T="abcdx";
cout<<BF(M,T,1)<<endl;
return 0;
}KMP算法正是从朴素算法改进而来：
#include<iostream>
#include<string>
using namespace std;
//返回子串T的next数组。注意数组作为形参是传的指针
int getnext(string T,int *next,int Tlong);
int KMP(string M,string T,int pos)
{
int i=pos;
int j=0;
int Mlen=M.size();//主串的范围[0,Slen)
int Tlen=T.length();//子串的范围[0,Tlen)
int next[255];//定义next数组 new
getnext(T,next,Tlen);//new
if(pos<0 && pos>Mlen)
return -1;
while(i<Mlen && j<Tlen)
{
if(M[i]==T[j])
{
++i;
++j;
}
else
{
j = next[j];//new
}
}
if(j>=Tlen)
return i-Tlen;
else
return -1;
}
int main()
{
string M="abcdefabcdx";
string T="abcdx";
cout<<KMP(M,T,1)<<endl;
return 0;
}
int getnext(string T,int *next,int Tlong){
int i,k;
i=1;
k=0;
next[1]=0;
while(i<Tlong){//T[0]是串T的长度
if(k==0||T[i]==T[k])
{
++i;
++k;
next[i] = k;
}
else
k=next[k];
}
}不过有点问题。
下面是验证通过版：
#include<iostream>
#include<string>
using namespace std;
int *getnext(string T);
int KMP(string M,string T)
{
int i,j;
int *next = getnext(T);
for(i=0,j=0;i<M.size() && j<(int)T.size();)
{
if(j==-1||M[i]==T[j])
{
++i;
++j;
}
else
{
j = next[j];//new
}
}
delete []next;
if(j==(int)T.size())
return i-j;
else
return -1;
}
int main()
{
string M="abcdefabcdx";
string T="abcdx";
cout<<KMP(M,T)<<endl;
return 0;
}
int *getnext(string T){
int j,k;
int *next = new int [T.size()];
j=0,k=-1;
next[j] = k;
while(j<T.size()){
if(k==-1||T[j]==T[k])
next[++j] = ++k;
else
k = next[k];
}
return next;
}KMP算法改进先略。