字符串

• 串(String)是由零个或多个祖父组成的有限序列,又叫做 字符串

• 传可以使空串

• 子串与主串,例如 "Matrix" 是 "Matrix42" 的子串,反之"Matrix42" 为 "Matrix" 的主串

字符串的比较

• 字符串比较大小跟传统的数字比较大小有点差别,很容易我们可以知道2比1要大,可是"matrix" 和 "Matrix42"呢?,要怎么比较呢?比长短还是比大小?

• 比大小!逼得就是字符串里每个字符的ASCII码的大小,因为'M'== 77 , 'f'==109,所以"matrix" > "Matrix42"

• 其实这样的比较大小没有多大意义,字符串的比较我们更重视是否相等!

字符串的存储结构

• 字符串的存储结构与线性表相同,也分顺序存储结构和链式存储结构

• 字符串的顺序存储结构使用一组地址连续的存储单元来存储串中的字符串序列的

• 按照预定义的大小,为每个定义的字符串变量分配一个固定长度的存储区,一般用定长数组来定义

• 与线性表相似,既然是固定长度的存储区,就存在一个空间分配不灵活的问题,那么会考虑用链式存储结构

• 不同的是字符串我们一般都是连在一起表述的,"断章取义"的情况并不多,所以习惯上我们通常还是会直接定义一个足够长度的存储区来存储的

BF(Brute Force)算法

• BF算法属于朴素的模式匹配算法,它的核心思想是:

  • 有两个字符串S和T,长度为N和M,首先S[1]和T[1]比较,若相等,则再比较S[2]和T[2],一直到T[M];若S[1]和T[1]不等,则T向右移动一个字符的位置,再依次进行比较

  • 该算法最坏情况下要进行M*(N-M+1)次比较,时间复杂度为O(M*N)

• 在这里S是主串,T是子串,这种子串的定位操作通常称作串的模式匹配

KMP算法

• KMP算法是三位老前辈(D.E.Knurh,J.HMorris和V.R.Paratt)的研究结果,大大的避免重复遍历的情况,全称叫做克努特-莫里斯-普拉特算法,简称KMP算法

• KMP算法的核心是避免不必要的回溯,问题由模式串决定,不是由目标串决定

KMP算法之next数组代码原理分析

• next数组:当模式匹配串T失配的时候,next数组对应的元素指导应该用T串的哪个元素进行下一轮匹配

j= 0;
i = 1;
next[1] = 0;
//T[0]为串的长度
while(i<T[0])
{
    //匹配上了
    if(j==0 || T[i] == T[j])
    {
        //前缀
        i++;
        //后缀
        j++;
        next[i] = j;
    }
    //失配
    else
    {
        //j回溯
        j = next[j];
    }
}

KMP算法之实现及优化

typedef char* String;

void get_next(String T,int *next)
{
    int j = 0;
    int i = 1;
    next[1] = 0;

    while(i<T[0])
    {
        if(0==j || T[i] == T[j])
        {
            i++;
            j++;
            if(T[i]!=T[j])
            {
                next[i] = j;
            }
            else
            {
                next[i] = next[j];
            }
        }
        else
        {
            j = next[j];
        }
    }
}

//返回子串T在主串S第POS个字符之后的位置
//若不存在,则返回0
int Index_KMP(String S,String T,int pos)
{
    int i = pos;
    int j = 1;
    int next[255];
    get_next(T,next);
    while(i<S[0] && j<=T[0])
    {
        if(0==j || S[i]==T[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    if(j>T[0])
    {
        return i-T[0];
    }
    else
    {
        return 0;
    }
}