4.1_1串的定义和基本操作

串的定义

串，即字符串（String）是由零个或多个字符组成的有限序列。一般记为S='a1a2·····an'(n≥0)
其中，s是串名，单引号括起来的字符序列是串的值；ai可以是字母、数字或其他字符；串中字符的个数n称为串的长度。n＝0时的串称为空串（用ø表示）。

S="HelloWorld!”
T='iPhone 11 Pro Max?'

子串：串中任意个连续的字符组成的子序列。 Eg：＇iPhone＇，＇ProM＇是串T的子串
主串：包含子串的串。 Eg：T是子串＇iPhone＇的主串
字符在主串中的位置：字符在串中的序号。 Eg：＇1＇在T中的位置是8（第一次出现）【从1开始】
子串在主串中的位置：子串的第一个字符在主串中的位置。 Eg：＇11 Pro＇在T中的位置为8

空串 M=‘’
空格串N=‘ ’ N是由三个空格字符组成的空格串，每个空格字符占1B

串V.S线性表

串是一种特殊的线性表，数据元素之间呈线性关系

串的数据对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等）
串的基本操作，如增删改查等通常以子串为操作对象

串的基本操作

假设有串T＝“”，S＝”iPhone 11 Pro Max?” W=“Pro”
StrAssign（＆T，chars）：赋值操作。把串T赋值为chars。
StrCopy（＆T，S）：复制操作。由串S复制得到串T。
StrEmpty（S）：判空操作。若S为空串，则返回TRUE，否则返回FALSE。
StrLength（S）：求串长。返回串S的元素个数。
ClearString（＆S）：清空操作。将S清为空串。
DestroyString（＆S）：销毁串。将串S销毁（回收存储空间）。
Concat（＆T，S1，S2）：串联接。用T返回由S1和S2联接而成的新串
SubString（＆Sub，S，pos，len）：求子串。用Sub返回串S的第pos个字符起长度为len的子串。
Index（S，T）：定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0。
StrCompare（S，T）：比较操作。若S＞T，则返回值＞0；若S＝T，则返回值＝0；若S＜T，则返回值＜0。

从第一个字符开始往后依次对比，先出现更大字符的串就更大

长串的前缀与短串相同时，长串更大

只有两个串完全相同时，才相等

“abandon”<“aboard”
“abstract”<“abstraction”
“academic”=“academic”

字符集编码

y=f(x)

字符集：函数定义域
编码：函数映射规则f
y:对应的二进制数

任何数据存到计算机中一定是二进制数。

字符集
英文字符——ASCII字符集
中英文——Unicode字符集

注：采用不同的编码方式，每个字符所占空间不同，考研中只需默认每个字符占1B即可。

4.1_2串的存储结构

串的顺序存储

#define MAXLEN 255	//预定义最大串长255
typedef struct{
    char ch[MAXLEN];	//每个分量存储一个字符	静态数组长度不可变（定长的顺序存储）
    int length;		//串的实际长度
}SString;

typedef struct{
    char *ch;	//按串长分配存储区，ch指向串的基地址	动态数组实现
    int length;	//串的长度
}HString;
HString S;
S.ch = (char *)malloc(MAXLEN*sizeof(char));		//用完需要手动free
S.length = 0;

串的链式存储

typedef struct StringNode{
	char ch;		//每个节点存一个字符——存储密度低，每个字符1B，每个指针4B
    struct StringNode *next;
}StringNode,*String;

typedef strunt StringNode{
    char ch[4];		//每个节点存多个字符
    struct StringNode *next;
}StringNode,*String;

最后一个节点没有填满，可以用其它字符代替

基本操作的实现

StrAssign（＆T，chars）：赋值操作。把串T赋值为chars。
StrCopy（＆T，S）：复制操作。由串S复制得到串T。
StrEmpty（S）：判空操作。若S为空串，则返回TRUE，否则返回FALSE。
StrLength（S）：求串长。返回串S的元素个数。
ClearString（＆S）：清空操作。将S清为空串。
DestroyString（＆S）：销毁串。将串S销毁（回收存储空间）。
Concat（＆T，S1，S2）：串联接。用T返回由S1和S2联接而成的新串

#define MAXLEN 255		//预定义最大串长为255
typedef struct{
    char ch[MAXLEN];		//每个分量存储一个字符
    int length;			//串的实际长度
}SString;

SubString(&Sub,S,pos,len)求子串。用Sub返回串的第pos个字符起步，长度为len子串

S.ch="wangdao";S.length=7;

bool SubString(SString &Sub,SString S,int pos,int len){
    if(pos+len-1 > S.length) return false;		//越界
    for(int i=pos;i<pos+len;i++) Sub.ch[i-pos+1]=S.ch[i];
    Sub.length = len;
    return true;
}

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

StrCompare(S,T)比较操作。S>T，返回值>0；S=T，返回值=0；S<T,返回值<0

int StrCompare(SString S,SString T){
    for(int i=1;i<=S.length && i<=T.length;i++){
		if(S.ch[i] != T.ch[i]) return S.ch[i] - T.ch[i];
    }
    return S.length-T.length;	//扫描过的所有字符都相同，则长度长的串更大
}

Index(S,T) 定位操作。主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0。

int Index(SString S,SString T){
    int i=1,n=StrLength(S),m=StrLength(T)；
    SString sub;
    while(i<=n-m+1){
        SubString(sub,S,i,m);
        if(StrCompare(sub,T)!=0)	++i;
        else return i;
    }
    return 0;
}

4.2_1朴素模式匹配算法

什么是字符串的模式匹配

子串——主串的一部分，一定存在
模式串——不一定能在主串中找到

字符串模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置。

朴素模式匹配算法

主串长度为n，模式串长度为m

朴素模式匹配算法：将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有的子串都不匹配为止。

最多对比 n - m＋1 个子串

若当前子串匹配失败，则主串指针i指向下一个子串的第一个位置，模式串指针j回到模式串的第一个位置

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

若j＞T.length，则当前子串匹配成功，返回当前子串第一个字符的位置——i-T.length

最坏的情况，每个子串都要对比m个字符，共n-m+1个子串，复杂度=O((n-m+1)m)=O(nm)

4.2_2KMP算法

不需要修改主串的i，不需要让主串的i回溯——回到开头

int Index_KMP(SString S,SString 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;
    }
}

对于模式串T ＝＇abaabc＇
当第6个元素匹配失败时，可令主串指针i不变，模式串指针j＝3
当第5个元素匹配失败时，可令主串指针i不变，模式串指针j＝2
当第4个元素匹配失败时，可令主串指针i不变，模式串指针j＝2
当第3个元素匹配失败时，可令主串指针i不变，模式串指针j＝1
当第2个元素匹配失败时，可令主串指针i不变，模式串指针j＝1
当第1个元素匹配失败时，匹配下一个相邻子串，令j＝0，i＋＋，j＋＋

4.2_3求next数组

求模式串的next数组（手算练习）

next数组的作用：当模式串的第j个字符失配时，从模式串的第next［j］的继续往后匹配

任何模式串都一样，第一个字符不匹配时，只能匹配下一个子串，因此，往后余生，next［1］都无脑写0

任何模式串都一样，第2个字符不匹配时，应尝试匹配模式串的第1个字符，因此，往后余生，next［2］都无脑写1

在不匹配的位置前边，划一根美丽的分界线模式串一步一步往后退，直到分界线之前“能对上”，或模式串完全跨过分界线为止

next[x] x代表模式串中第几个数不匹配
j代表回溯到模式串中的哪个位置——j等于0的时候执行 ++i; ++j; //继续比较后继字符

模式串T=ababaa

序号j	1	2	3	4	5	6
模式串	a	b	a	b	a	a
next[j]	0	1	1	2	3	4

int Index_KMP(SString S,SString 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;
    }
}

4.2_4KMP算法的进一步优化