字符串

串的存儲(chǔ)結(jié)構(gòu)

1.定長(zhǎng)順序存儲(chǔ)表示
用一組地址連續(xù)的存儲(chǔ)單元

#define MAXLEN 255
typedef struct{
    char ch[MAXLEN];
    int length;
}SString;

2.堆分配存儲(chǔ)表示
仍以一組地址連續(xù)的存儲(chǔ)單元存放，但存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配的

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

C語(yǔ)言中存在一個(gè)稱(chēng)為堆的自由存儲(chǔ)區(qū)，并用malloc()和free()函數(shù)來(lái)完成動(dòng)態(tài)存儲(chǔ)管理
上述兩種方式通常為高級(jí)程序設(shè)計(jì)語(yǔ)言采用
3.塊鏈存儲(chǔ)表示
采用鏈表方式存儲(chǔ)串值
在具體實(shí)現(xiàn)時(shí)每個(gè)結(jié)點(diǎn)即可以存放一個(gè)字符，也可以存放多個(gè)字符。每個(gè)結(jié)點(diǎn)稱(chēng)為塊，整個(gè)鏈表稱(chēng)為塊鏈結(jié)構(gòu)。

串的基本操作

StrAssign(&T, chars) "賦值操作，把串T賦值為chars"
StrCopy(&T, S)
StrEmoty(S) "判空"
StrCompare(S,T)
StrLength(S)
SubString(&Sub, S, pos, len) "求子串，用Sub返回S的第pos個(gè)字符起長(zhǎng)度為len的子串"
Concat(&T, S1, S2) "聯(lián)接"
Index(S, T, pos) "定位子串T，第pos個(gè)字符之后第一次出現(xiàn)的位置"
Replace(&S, T, V) "替換子串"
StrInsert(&S, pos, len) "插入子串"
StrDelete(&S, pos, len)
ClearString(&S)
DestroryString(&S)

串的模式匹配

子串的定位操作，子串通常稱(chēng)為模式串

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;
}

最壞時(shí)間復(fù)雜度O(nm)

改進(jìn)的模式匹配算法——KMP
利用比較過(guò)的信息，i指針不需要回溯，僅將子串向后滑動(dòng)一個(gè)合適的位置，并從這個(gè)位置開(kāi)始和主串進(jìn)行比較，這個(gè)合適的位置僅與子串本身的結(jié)構(gòu)有關(guān)，而與主串無(wú)關(guān)。
前綴，后綴，部分匹配值

前綴后綴部分匹配值.PNG

KMP過(guò)程.PNG

計(jì)算機(jī)求next數(shù)組的方法

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];
    }
}

求next.PNG

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;
}