数据结构与算法-串

2020-04-29 本文已影响0人卡布奇诺_95d2

一、串的基本概念

1、串是由零个或多个字符组成的有限序列，又名叫字符串。
2、一般记为s="a₁a₂a₃...a_n（n>=0）"；其中s是串的名称，用双引号括起来的部分就是字符序列的值。
3、串中的字符数目n称为串的长度；
4、零个字符的串称为空串，它的长度为零，用""表示；
注意：空格串是只包含空格的串，空格串是有内容有长度的，而且还可以有多个空格。
5、对于两个不相等的字符串，如何判断它们的大小，判断依据如下：
给定两个字符串，
s="a₁a₂a₃a₄...a_n"
t="b₁b₂b₃b₄...b_m"
（1）当n<m且a_i=b_i(i=1,2...n)。此时就说s<t。例如：s="hap"，t="happy"。此时s<t；
（2）存在某个k<=min(m,n)，使得a_i=b_i(i=1,2...k-1)，a_k<b_k。此时也说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(S_i-m+1...S_i) = S_i-m+1*D^m-1 + S_i-m+2*D^m-2 + ... + S_i-1*D + S_i
其中：D：表示进制；

2、主串拆解的子串哈希值求解规律

每次比较都对主串中的子串进行hash求解，那时间算法复杂度为O(m)。如果可以利用上一个子串的hash结果hash(S_i-m+1...S_i)，在O(1)的时间内求出下一个子串的hash(S_i-m+2...S_i+1)，则可以将整体复杂度降低到线性时间。
根据hash函数可以得到：
hash(S_i-m+2...S_i+1) = S_i-m+2 *D^m-1 + S_i-m+3 *D^m-2+ ... + S_i *D + S_i+1
= (hash(S_i-m+1...S_i) - S_i-m+1 *D^m-1) * D + S_i+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)。

数据结构与算法-串

一、串的基本概念

二、字符串的抽象数据类型

三、模式匹配算法

1、朴素的模式匹配算法（BF算法）

BF算法代码

BF算法效率分析：

RK算法

1、字母换算成哈希值

2、主串拆解的子串哈希值求解规律

3、代码实现

猜你喜欢

热点阅读