串

串即字符串，由一个或多个字符组成的有限序列
串是一种特殊线性表，限制了数据类型的线性表，数据间关系成线性关系
串为了方便算法设计，第一个字符存放的下标可以从1开始

串的基本操作

void StrAssign(&T,chars); //赋值操作
void strCopy(&T,S); //复制操作
bool StrEmpty(S); //判空操作
int StrCompare(S,T); //比较操作
int StrLength(S); //计算串长
void Concat(&T,S1,S2); //串联结
int Index(S,T); //定位子串T在主串S中的位置
void ClearString(&S); //清空操作
void DestroyString(&S); //销毁操作

字符集编码

英文字符一般使用ASCII字符集，每个字符仅占1B，有效序号为0-127

其他字符集，例如Unicode字符集。每种字符集可以由多种编码方案，例如Unicode字符集可以采用UTF-8、UTF-16两种不同的方案
不同的字符集、编码方案会导致每个字符占用的空间不同，考研中默认统一每个字符占1B

暴力匹配法(朴素模式匹配算法)

朴素模式匹配算法

假定主串长度为n，匹配串长度为m
将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串或所有子串都不匹配为止
至多匹配n-m+1个子串

算法过程

从主串S第一个字符开始，与模式串T的第一个字符比较，若相同则比较下一个字符；否则从主串的下一个字符起，重新与模式串中的字符进行比较
直到模式串中的每个字符依次在主串中匹配到，则说明匹配成功，并返回匹配成功时子串第一个字符的序号；若最后匹配失败返回0

至多运算(n-m+1)m=nm+m-m^2次，一般m<<n，所以最坏时间复杂度O(mn)

KMP算法

在朴素模式匹配算法中，当匹配模式串中间字符过程中发生匹配失败，直接回溯主串下一个字符往往会出现重复匹配，造成时间浪费

kmp算法在回溯方面进行优化改进，当模式串第一个字符匹配失败，主串指针+1，模式串指针回溯到1；当模式串中间字符匹配失败，主串指针不变，模式串指针回溯相应位置即可
为了方便回溯，可直接将不同匹配失败的回溯位置直接存放在next数组中，当发生匹配失败直接回溯模式串指针即可

//kmp算法
int Index_KMP(SString S,SString T,int next[]){
    //规定指针下标从1开始
    int i=1,j=1;
    while(i<=S.lenght && j<=T.length){
        //模式串匹配结束说明匹配成功，否则直到主串匹配结束说明匹配失败
        if(!j || S.data[i]==T.data[j])
            //顺利匹配，主串、模式串指针均后移
            //若上一次模式串第一个字符匹配失败，模式串指针后移j=0->j=1,主串指针后移
            i++,j++;
        else
            //若匹配失败，模式串指针回溯，主串指针不动
            j=next[j];
    }
    if(j>T.length)
        //模式串指针越界说明匹配成功，直接返回匹配子串首字符序号
        return i-T.length;
    else 
        //匹配失败返回0
        return 0;
}

求模式串next数组

考研暂不要求算法实现，但需要掌握手算方法，next数组长度与模式串长度m相同，并且下标从1开始

next数组的作用是当发生匹配失败时，模式串指针需要回溯到合适的位置以加快效率，同时显然任何模式串next数组的第一个位置的值都是确定的next[1]=0

同时分析，当第二个字符匹配失败时，任何模式串一定会尝试匹配第一个字符，显然next[2]=1

其余位置匹配失败需要逐步分析

假定模式串第j位置上匹配失败，那么主串[i-j+1]~[i-1]位置上的每个字符与模式串[1]~[j-1]位置上的字符是一一对应的
此时，模式串指针j依次-1，重新匹配主串[i-j+1]~[i-1]位置上的字符是否和模式串[1]~[j-1]位置上的字符是否对应，如果对应，则将j的值填入next数组中;否则，直接把1填入next数组

显然可以确定，除了next[0]、next[1]的值是确定的，其余位置的值都是与模式串本身相关

next数组手算方法算法实现

//字符串比较
bool strcomp(SString S1,SString S2,int lenth){
    int i;
    for(i=1;i<lenth;i++)
        //如果匹配失败，直接跳出循环
        if(S1.data[i]!=S2.data[i]) break;
    //若匹配成功，i的值为子串长度，反之说明匹配失败
    return i==lenth;
}

//求next数组算法
void Next_KMP(SString T,int next[]){
    //规定指针下标从1开始
    int i=1;
    //next[1]=0，并且循环从next[2]开始
    next[i++]=0;
    while(i<=T.length){
        int j;
        for(j=1;j<i;j++)
            if(strcomp(T,T+j,i-j)) break;
        next[i]=i-j;
        i++;
    }
}

上述手算方法，由于考题的规模比较小，人眼看子串是否匹配更加高效，但是对于计算机而言时间复杂度为反而更高了（执行次数为$1²⁺²+...m^2$）

对于计算机去求解next数组，更加适合以下实现方式

假设next[j]=k,此时next[j+1]有两种情况

• 新增的j字符和k字符相同，即继续重复出现前缀如aaaaaa,显然有next[j+1]=next[j]+1=k+1
• 新增字符和之前的字符均不相同,如aaaaab,那么由于不存在更短的相同前缀，可以直接确定next[j+1]=next[j]

//求next数组算法
void Next_KMP(SString T,int next[]){
    //规定i指针下标从1开始
    //指针j用于统计之前连续相同字符的数量，j=0将next[1]情况跳过
    int i=1,j=0;
    //初始化next[1]=0
    next[1]=0;
    while(i<T.length){
        //由于next数组i先+1后存值，因此循环条件为length-1
        if(!j || T.data[i]==T.data[j]){
            //j==0确保next[1]=1的值填入
            //j==1后，j=i-1，每次只要比较前后字符是否相同，相同则j++,实现next[i+1]=next[i]+1,同时j为当前连续相同前缀字符数量
            i++,j++;
            next[i]=j;
        }
        else
            //当前后字符不同时，连续前缀数量并不发生改变，直接继承之前的数量，next[i+1]=j
            j=next[j];
    }
}

总结起来，KMP算法最坏时间复杂度为O(m+n)，其中求next数组时间复杂度为O(m),模式匹配最坏时间复杂度为O(n)

朴素匹配算法最坏情况比kmp算法要慢，但是一般情况下朴素匹配算法时间复杂度也为O(m+n),只有出现主串和子串有很多部分匹配的情况下效率更高

KMP改进算法

在next数组中，如果在j位置发生匹配失败后，指针j会跳到next[j]位置，但是如果T[j]==T[next[j]],即跳转后的字符和之前一样的情况，那么依旧会发生匹配失败，指针j可以再跳到next[next[j]]，从而达到进一步优化

这一步改进优化，实质上时对next数组的值进行优化，匹配算法不需要修改，即如果模式串中j位置的字符与next[j]位置的字符相同，可以直接赋值next[j]=next[next[j]]

//求nextval数组算法
void Next_KMP(SString T,int nextval[]){
    //规定i指针下标从1开始
    //指针j用于统计之前连续相同字符的数量，j=0将next[1]情况跳过
    int i=1,j=0;
    //初始化next[1]=0
    next[1]=0;
    while(i<T.length){
        //由于next数组i先+1后存值，因此循环条件为length-1
        if(!j || T.data[i]==T.data[j]){
            //j==0确保next[1]=1的值填入
            //j==1后，j=i-1，每次只要比较前后字符是否相同，相同则j++,实现next[i+1]=next[i]+1,同时j为当前连续相同前缀字符数量
            i++,j++;
            if(T.data[i]==T.data[j])
                //当j位置的字符和当前字符相同时，由于仍旧会匹配失败，直接访问nextval
                nextval[i]=nextval[j];
            else
                //相反，和之前的方式相同
                nextval[i]=j;
        }
        else
            //当前后字符不同时，连续前缀数量并不发生改变，直接继承之前的数量，next[i+1]=j
            j=nextval[j];
    }
}

以上确实对kmp算法进行了优化，但是时间复杂度上分析依旧是O(m+n)，主要是对模式串中子串部分匹配问题进行了优化，一般情况下效率相差不多