串

串是由零个或者多个字符组成的有限序列

定长顺序存储

堆分配存储

malloc

free

块链存储

一个节点可以存放一个字符，也可以存放多个字符

普通算法时间复杂度为O(m*n)

KMP算法

手动算法

对于字符串 “ababa”

a的前缀和后缀都是空集

“ab”的前缀和后缀交集为空

”aba“ 前缀 {a,ab} 后缀{ba,a} 交集为{a}，最长相等前后缀长度为1

”abab“ 前缀{a,ab,aba} 后缀{b,ab,bab} 交集为{ab}，最长相等前后缀长度为2

”ababa“ 前缀{a,ab,aba,abab} 后缀{baba,a,aba,ba} 交集为{aba,a}，最长相等前后缀长度为3

部分匹配值为 00123

移动位数=已经匹配的字符数-对应的部分匹配值

Move= （j-1)-PM[j-1]

编号 1 2 3 4 5
S a b a b a
PM 0 0 1 2 3

改进一下

Move= （j-1)-next[j]

PM右移一位

编号 1 2 3 4 5
S a b a b a
PM -1 0 0 1 2

改进一下

j=j-move=next[j]+1

编号 1 2 3 4 5
S a b a b a
next 0 1 1 1 2

next[j]表示当字串第j个字符和主串发生失配时，跳到字串的next[j]位置重新与主串当前位置进行匹配

算法时间复杂度为O(m+n)

1
2
3
4
5
6
7
8
9
10
11
12
13
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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int Index_KMP(string S,string T,int next[]){
    int i=1,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;
}

KMP优化

1
2
3
4
5
6
7
8
9
10
11
12
13
void get_nextval(string T,int next[]){
    int i=1,j=0;
    nextval[1]=0;
    while(i<T.length){
        if(j==0 || T.ch[i]==T.ch[j]){
            i++;j++;
            if(T.ch[i]!=T.ch[j]) nextval[i]=j;
            else nextval[i]=nextval[j];
        }
        else:
        	j=nextval[j];
    }
}