数据结构——串

KMP算法

串

定义：由0个或多个字符组成的有限序列，记为

1. 若两个串的长度相等且每个对应位置的字符都相等时，称这两个串时相等的
2. 子串：串中任意个连续的字符组成的子序列成为字串
3. 主串：包含子串的串为主串

存储结构

定长顺序存储结构

#define MAXLEN 25
typedef struct{
    char ch[MAXLEN];	// 字符类型数组
    int length;			// 数组长度，超过部分舍去
}SString;

\\0：字符串的结束

堆分配存储表示

typedef struct{
    char *ch;
    int length;
}HSting;

malloc()/free()

块链存储结构

利用链表来存储字符串

基本操作

最小操作子集

• 赋值（StrAssign(&T, chars)）

• 比较（StrCompare(S, T)）

• 串长（StrLength(S)）

• 子串（SubString(&Sub, S, pos, length)）

• 联接（Concat(&T, S1, S2)）

模式匹配

int Index(SString S, SString T, int pos){
    int i=pos,j=1;
    while(i<S.length && j<=T.length){
        if(S.ch[i]==T.ch[j]){
            i++;
            j++;
        }
        else{
            i=i-j+2;
            j=1;
        }
        if(j>T.length)
            return i-T.length;
        else
            return 0;
    }
}

KMP算法

1. 前缀：除最后一个字符外，字符串所有头部子串

2. 后缀：除第一个字符外，字符串所有的尾部子串

3. 部分匹配值：字符串前缀和后缀最长相等前后缀的长度——移动步长

   

   

4. next数组存储

   

   

   右移：1）第一个元素右移后变为-1；2）最后一个元素右移后直接舍去

   

5. 

void get_next(String T, int next[]){
    int i=1,j=0;
    next[1]=0;
    while(i<T.length){
        if(j==0 || T.ch[i]==T.ch[j]){
            ++i;++j;
            next[i]=j;
        }else
            j=next[j];
    }
}

KMP

int Index_KMP(String S, String T, int next[], int pos){
    int i=pos,j=1;
    while(i<=S.length && j<=T.length){
        if(j==0 || S.ch[i]==T.ch[j]){
            i++;
            j++;
        }
        else
            j=next[j];
    }
    if(j>T.length)
        return i-T.length;
    else
        return 0;
}