数据结构算法字符串

字符串

定义和基本操作

定义

由零个或多个字符组成的优先序列

基本操作

StrAssign(&T, chars) 赋值。把字符串T赋值为chars
StrCopy(&T, S) 复制。由S复制到T
StrEmpty(S) 判空
StrLength(S) 求长度
ClearString(&S) 清空
DestroyString(&S) 销毁。回收存储空间
Contact(&T,&T1,&T2) 联接，返回S1和S2联接的新串
SubString(&sub, S, pos, len) 求子串，第pos字符开始长度为len的子串
Index(S,T) 定位操作，返回S中存在T相同的子串的位置，否则返回-1
StrCompare(S,T) 比较操作

字符集编码

任何数据在计算机中一定是二进制
字符集：英文字符，ASCII字符，中英文，Unicode字符集
基于同一个字符集可以有不同编码方式：UTF-8，GBK
不同的编码方式，字符占用的空间不同

存储结构

顺序存储

方案1: 一个数组存储字符，一个int变量存储实际长度
方案2: 数组的ch[0]充当长度，优点：字符的位序和数组下标相同
方案3: 没有长度变量，已字符’\0’表示结尾，缺点：获取长度需要遍历
方案4: ch[0]废弃不用，外加一个长度变量

链式存储

基本操作实现-第四种方案

匹配问题-朴素算法

方法1

将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有子串都不匹配为止
主串长度为n，模式串长度为m，最多对比 n - m + 1个子串

方法2

使用两个指针i和j进行匹配，如果当前子串匹配失败，则主串指针i指向下一个子串的第一个位置，模式串指针j回到模式串的第一个位置，即 i = i - j + 2; j = 1;

如果 j > T.length, 则当前串匹配成功，返回第一个字符的位置即 i - T.length

int Index(SString S, SString T) {
int i = 1, 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 -1;
}
}

匹配问题-KMP算法

原理：减少i指针的回溯，通过已经计算好的next指针，提高算法效率
精髓：利用好已经匹配过的模式串信息
next数组记录了当第几个元素匹配失败的时候，j的取值

步骤

根据模式串T，求出next数组
利用next数组进行匹配（主串指针不回溯）

求next数组

当模式串的第j个字符匹配失败时，从模式串的第next[j]的继续往后匹配

步骤

第一个字符不匹配时，只能匹配下一个子串，因此next[1]都无脑写0if(j==0){i++;j++}
第二个字符不匹配时，应尝试匹配模式串的第一个字符，因此next[2]都无脑写1

第三个字符及之后的，在不匹配的位置前边，划一根美丽的分界线模式串一步步往后退，直到分界线之前能对上，此时j指向哪儿，next数组值就是多少

void get_next(SString 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];
    }
}
}