一、串的基本概念
1、串是由零个或多个字符组成的有限序列，又名叫字符串。
2、一般记为s="a1a2a3...an（n>=0）"；其中s是串的名称，用双引号括起来的部分就是字符序列的值。
3、串中的字符数目n称为串的长度；
4、零个字符的串称为空串，它的长度为零，用""表示；
注意：空格串是只包含空格的串，空格串是有内容有长度的，而且还可以有多个空格。
5、对于两个不相等的字符串，如何判断它们的大小，判断依据如下：
给定两个字符串，
s="a1a2a3a4...an"
t="b1b2b3b4...bm"
（1）当n<m且ai=bi(i=1,2...n)。此时就说s<t。例如：s="hap"，t="happy"。此时s<t；
（2）存在某个k<=min(m,n)，使得ai=bi(i=1,2...k-1)，ak<bk。此时也说s<t。例如：s="happen"，t="happy"。此时s<t。
二、字符串的抽象数据类型
串的逻辑结构和线性表很相似，不同之处在于串针对的是字符集，也就是串中的元素都是字符，因此串的基本操作与线性表的操作还是有区别的。线性表更关注单个元素的操作，比如查找一个元素、插入或删除一个元素等，而串更多的是查找子串的位置、得到指定子串的位置，替换子串等操作。
以下用代码实现一下串的基本操作。
/* 生成一个其值等于字符串常量chars的串T */
Status StrAssign(String T,char *chars){
if(strlen(chars) > MAXSIZE) return ERROR;
T[0] = strlen(chars);
for(int i = 1; i<=T[0]; i++){
T[i]=chars[i-1];
}
return OK;
}
/*串S存在，由串S复制得到串T*/
Status StrCopy(String T, String S){
if(S == NULL || S[0] <= 0 || S[0]>MAXSIZE) return ERROR;
int temp = T[0];
T[0] += S[0];
for(int i=temp+1; i<=T[0]; i++){
T[i] = S[i-temp];
}
return OK;
}
/*串S存在，将串清空*/
Status ClearString(String S){
S[0] = 0;
return OK;
}
/*若串S为空，返回true，否则返回false*/
BOOL StringEmpty(String S){
if(S[0] <= 0) return YES;
return NO;
}
/*返回串S的元素个数，即串的长度*/
char StringLength(String S){
return S[0];
}
/*若S>T，返回值>0，若S=T，返回0，若S<T，返回值<0*/
int StrCompare(String T, String S){
int i = 0;
if(S[0]<T[0]){
return -1;
}
for(i = 0; i<T[0] && i<S[0]; i++){
if(T[i+1]<S[i+1]){
return 1;
}
else if(T[i+1]>S[i+1]){
return -1;
}
}
if(i == T[0] && i == S[0]) return 0;
if(i==T[0] && i<S[0]) return -1;
if(i==S[0] && i<T[0]) return 1;
return 0;
}
/*串S存在，1<=pos<=StrLength(S)，且0<=len<=StrLength(S)-pos+1，用Sub返回串S的第pos个字符起长度为len的子串*/
Status SubString(String Sub, String S, int pos, int len){
if(S == NULL || S[0] <= 0) return ERROR;
if(pos<0 || pos>S[0]) return ERROR;
if(len<0 || (len+pos-1)>S[0]) return ERROR;
Sub[0] = len;
for(int i = 1; i<=len; i++){
Sub[i] = S[pos++];
}
return OK;
}
/*用T返回由S1和S2联接而成的新串*/
Status Concat(String T, String S1, String S2){
if(S1 == NULL || S1[0] <= 0){
if(S2 != NULL && S2[0]<MAXSIZE){
return StrCopy(T, S2);
}
else{
return ERROR;
}
}
else if(S2 == NULL || S2[0] <= 0){
if(S1 != NULL && S1[0]<MAXSIZE){
return StrCopy(T, S1);
}
else{
return ERROR;
}
}
if(S1[0]+S2[0]>MAXSIZE) return ERROR;
StrCopy(T, S1);
StrCopy(T, S2);
return OK;
}
/*串S和T存在，T是非空串，1<=pos<=StrLength(S)。
若主串S中存在和串T值相同的子串，则返回它在主串中S的第pos个字符之后第一次出现的位置，否则返回0*/
int Index(String T, String Sub, int pos){
if(T == NULL || T[0]<=0) return ERROR;
if(Sub == NULL || Sub[0]<=0) return ERROR;
if(pos<0 || pos>T[0]) return ERROR;
String temp;
while((pos+Sub[0]-1)<=T[0]){
SubString(temp, T, pos, Sub[0]);
if(StrCompare(temp, Sub) == 0){
return pos;
}
pos++;
}
return 0;
}
三、模式匹配算法
子串的定位操作通常称为串的模式匹配。这应该是串最重要的操作之一。
1、朴素的模式匹配算法（BF算法）
例如，我们需要从主串S="goodgoogle"中，找到T="google"这个子串的位置。
1、主串S第一位开始，S与T前三个字母都匹配成功，但S的第四个字母d与T的第四个字母g匹配失败。
image.png
2、主串S第二位开始，主串S首字母是o，而子串T的首字母是g，匹配失败。
image.png
3、主串S第三位开始，主串S的首字母是o，仍然不与子串的首字母g匹配。
image.png
4、主串S第四位开始，主串S的首字母是d，子串首字母是g，匹配失败。
image.png
5、主串第5位开始，S与T，6个字母全部匹配，匹配成功。
image.png
简单来说，就是对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配，对主串做大循环，每个字符开头做T的长度的小循环，直到匹配成功或全部遍历完成。
BF算法代码
int Index(String T, String Sub, int pos){
if(T[0] < Sub[0]) return 0;
int i = pos;//i用于主串S中当前下标，若pos不为1，则从pos位置开始
int j = 1;//j用于子串T的当前位置下标值
while(i<=T[0] && j<=Sub[0]){
if(T[i] == Sub[j]){//主串和子串中两字母相同，则继续下位的字母比较
i++;
j++;
}
else{
i = i-j+2;//主串回到上次匹配的首位的下一位，即主串上次匹配的位置是3，则下次主串从第4个字符开始比较
j = 1;
}
}
if(j>Sub[0]){
return i-Sub[0]+1;
}
return 0;
}
BF算法效率分析：
BF算法中，
最好的情况是第一个字母之后就完全匹配，时间复杂度为0(1)，比如S="googlegood"，T="google"。
稍差一点的情况，如上述图中的示例，S="goodgoogle"，T="google"，时间复杂度为O(m+n)，m为主串长度，n为子串长度。
最差的情况，就是每次不成功的匹配都发生在串T的最后一个字符。如：S="0000000000000000000000000001"，T="000001"；最坏情况的时间复杂度为O((m-n+1)*n)。
由上述分析可知，BF算法太低效了，
RK算法
假设我们有某个hash函数可以将字符串转换为一个整数，则hash结果不同的字符串肯定不同，但hash结果相同的字符串则很有可能相同（存在小概率不同的可能）。
按照这个思路，我们可以将主串分割成n个长度为m的子串，并对每个子串进行hash计算，得到每个子串对应的hash值。再将每个子串的hash值与需要匹配的字符串的hash值进行比较。
image.png
根据RK算法核心思想，接下来分步对RK思想进行解析。
1、字母换算成哈希值
设计hash函数：
hash(Si-m+1...Si) = Si-m+1*Dm-1 + Si-m+2*Dm-2 + ... + Si-1*D + Si
其中：D：表示进制；
2、主串拆解的子串哈希值求解规律
每次比较都对主串中的子串进行hash求解，那时间算法复杂度为O(m)。如果可以利用上一个子串的hash结果hash(Si-m+1...Si)，在O(1)的时间内求出下一个子串的hash(Si-m+2...Si+1)，则可以将整体复杂度降低到线性时间。
根据hash函数可以得到：
hash(Si-m+2...Si+1) = Si-m+2 *Dm-1 + Si-m+3 *Dm-2 + ... + Si *D + Si+1
= (hash(Si-m+1...Si) - Si-m+1 *Dm-1) * D + Si+1
3、代码实现
/*由于字符串是26个英文字母，为了最大概率减少hash重复，定义进制为26进制*/
#define D 26
/*计算hash函数
如当abc转成hash时，
abc=a*D^2+b*D^1+c*D^0
*/
long caluHash(char* S, int num){
long hashValue = 0;
for(int i = 0; i < num; i++){
hashValue = (hashValue*D+ (S[i] - 'a'));
}
return hashValue;
}
/*用来获取hash值计算时的进制高位，
当字符串长度为m时，进制高位为D^(m-1)
在计算下一个子串时，需要用到
*/
int getMaxValue(int m){
int h = 1;
for(int i = 0;i < m - 1;i++){
h = (h*D);
}
return h;
}
/*定义一个匹配函数，用来验证给定长度为m的子串确实等于主串中i位置之后的m个字符串*/
int isMatch(char *S, int i, char *P, int m){
int is = i;
int ip = 0;
for(is=i, ip=0; is!=m && ip!=m;is++,ip++){
if(S[is] != P[ip]){
return 0;
}
}
return 1;
}
int RK(char *S, char *P){
if(S == NULL || P == NULL) return -1;
int n = (int)strlen(S);
int m = (int)strlen(P);
long sHash = caluHash(S, m);
long pHash = caluHash(P, m);
long hValue = getMaxValue(m);
for(int i = 0; i<=(n-m); i++){
if(sHash == pHash) {
if(isMatch(S, i, P, m)){
return i+1;
}
}
//RK算法核心，通过前一个子串推导后一个子串的hash值
sHash = ((sHash-(S[i]-'a')*hValue)*D+(S[i+m]-'a'));
}
return -1;
}
总结：可以看出，RK算法可以在线性时间内完成匹配，RK算法时间稍慢的原因主要有hash结果相同不一定完全匹配，需要再逐字符进行对比。时间复杂度精确值应为O(n) + O(m*n)。
网友评论