串

基本概念

串是零个或多个字符的有限序列。显然，串是一种线性表。显然，串是一种线性表。串中任意多个国家统计局的字符组成的子序列称为该串的子串，特别地，空串是任何串的子串。任意串S都是自身的子串，除S本身以外的S的其他子串为S的真子串。

串的存储：顺序存储与紧缩顺序存储。还有不必移动内存块的链接存储。

串运算

CMyString.h

#define MAX_STRING_SIZE 1024

struct cMyString
{
    int length;
    char str[MAX_STRING_SIZE+1]
};
typedef struct cMyString CMyString;

void InitCMyString(CMyString *, char *s);
/*初始化函数，构造一个字符指针所指的串*/
void Concatenate(CMyString *, CMyString *s);
/*将字符串s附加到本字符串之后*/
void InsertS(CMyString *, int pos, CMyString *s);
/*将字符串s插入到本字符串pos所指的位置*/
void DeleteS(CMyString *, int pos, int len);
/*删除从pos起的连续len个字符*/
CMyString SubString(CMyString *, const int pos, const int len);
/*提取一个字符串，从pos位置起长度为len的字符*/
char *GetString(CMyString *);
/*获取本字符串*/
int Find(CMyString *, CMyString *s);
/*查找字符串s首次出现的位置，如果不包含s则返回0*/

模式匹配

朴素的模式匹配

挨个比较，不对后移再挨个比较。

KMP匹配算法

一知半解，不知道为什么

简单而言：

KMP 算法借助于一个辅助数组next，来确定当匹配过程中出现不等时，P右移的位数和开始比较的字符位置。在这个数组中，next[i]的取值只与P的前i+1个字符本身相关，而与目标T无关。在匹配过程中，一旦遇到$p_j$和$t_j$比较时不相等，则∶若 $next[i] \ge 0$，应将P右移i-next[i]个字符，用P中第 next[i]个字符与$t_j$进行比较;若next[i]=-1，P中任何字符都不必再与t;比较，而应将 P右移i十1个字符，从$p_0$和$t_{j+1}$开始重新进行下一趟比较。

一旦计算出与P相关的next数组，则基于next数组的上述含义，可以很容易地给出串的匹配算法。

int Find(CMyString *CS, CMyString *s){
    int i, j, *next = (int *)malloc(sizeof(int) * s->length);

    /*构造模式s的next数组，详见下面的求next数组的算法*/
    GenKMPNext(next, s);
    for(i=0,j=0;i<s->length&&j<CS->Length){
        if (s->str[i]==CS->str[j])/*相等*/
            {i++;j++;}
        else if(next[i]>=0)/*不相等且next[i]>=0*/
            i=next[i];/*i减少j-i变大，右移*/
            else
                {i=0;j++;}/*同上*/
    }
    if(i>=s->length)
        return j-s->length;/*匹配成功，返回子串的起始位置*/
    else
        return -1;/*匹配失败，返回-1*/
}

• 注意，在匹配算法中，右移位数是由$p_i$与$t_j$共同决定的，j-i的值即为$p_0$的位置，所以比较前后的j-i可知移位多少。

next数组的计算方法

void GenKMPNext(int *next, CmyString *s)
{
    int i=0,j=-1;
    next[0] = -1;
    while(i<s->length-1)
    {
        /*找出p0,p1....pi中最大的相同的最左端子串和最右端子串*/
        while (j>=0&&s->str[i]!=s->str[j])
            j=next[j];
        i++;j++;
        if(s->str[i]==s->str[j])
            next[i]=next[j];
        else next[i]=j;
    }
}

算法效率分析：

算法效率分析∶
记 P 的长度为m，目标 T 的长度为n，则 KMP 匹配算法的时间复杂性分析如下∶整个匹配算法由 Find()和 GenKMPNext()两个部分的算法组成。在 Find())中包含一个循环，j的初值为0，每循环一次j的值严格增加1，直到j等于n 时循环结束，故循环执行了 n 次。在GenKMPNext()中，表面上有两重循环，时间复杂性似乎为O(m²)，其实不然，GenKMPNext()的外层循环恰好执行 m—1次;另外，j的初值为-1，外层循环中每循环一次，j的值增加1，同时，在内层循环中j被减小，但最小不会小于一1，因此，内层循环中j=next[j]语句的总的执行次数应小于或等于j的值在外层循环中被增加1 的次数，亦即在算法GenKMPNext()结束时，j=next[j]被执行的总次数小于等于 m-1次。

综上所述，对于长度为 m 的模式P和长度为n 的目标 T的模式匹配，KMP算法的时间复杂性为 O(m+n)。

BM匹配算法

也没太看懂

由一个数组变成了两个，同时从右向左比较。

以模式P="at_that"为例，其长度m=7，BM匹配算法中的第1个数组是delta1，该数组指出字符集中的每个字符在模式中相对于最右端的距离，用*代表任何一个未出现在模式中的字符，则对于给定的模式P，有∶

首先令delta2[7]=1，对于任意的k=6,5,...,2,1，考虑子串$s=p_{k+1}p_{k+2} \cdots p_7$(即$p_k$右边的子串，而不是从$p_k$算起)，相对于模式而言依次向左移动子串s，如果子串s没有匹配上，则继续向左移动子串s，直到匹配或者无法匹配（s的最左端字符移出到模式的最左端），记匹配或者无法继续匹配之前子串s移动的位数为n，则：delta2[k]=7-k+n

匹配时，首先将模式和目标左对齐，从模式最右端开始向左比较，匹配过程中，一旦$p_i$和$t_j$不相等，计算k=max(delta[ t[j] ], delta2[i])，并将P右移k+i-m位(m为模式串的长度)，用$p_m$和$t_{j+k}$继续比较。