算法基础-字符串与模式匹配

串和字符串

串是由零个或多个单独的元素组成的有限长序列.

在计算机中,串的最广泛的用处是字符串,因此一般情况下,串和字符串是等价的,字符串也简称为串,串就是字符串

串的结构

串实际上是一个特殊的数组,它的元素一定是字符类型的,因此他也具有数组所拥有的特性

读取字符串中的一个字符的时间复杂度是O(1),因为可以直接使用地址准确定位,修改字符串当中的一个字符也非常快,但是字符串无法动态地延长或减短,因为数组的长度是固定的

实际上在C语言中,字符串是一个char[]类型的变量,并且以“\0”为结尾,你可以通过修改“\0”的位置来增长或减短字符串,但是这只是一个停止标志,它所占用的空间仍然是不变的,如果你把“\0”移动到数组外面,那么系统会把本不属于它的内存读进去,造成显示异常

在更多的语言中,字符串并不是一个单纯的数组,而是一个构造复杂的类,其中包括了一个数组.并且字符串一旦被创建就再也无法修改,你只能在它的基础上构造新的字符串

子串

由串中任意个连续字符所组成的新字符串,称为原字符串的子串,例如“345”是“123456”的子串,同时任意字符串总是自己的子串

串的储存

堆存储

这种存储方法的特点是,字符串以一维数组的方式存放在堆中,但是数组长度并不固定,而是视字符串长度改变

class HString{
public:
    char* ch;
    int length;
    //使用原有字符串构造HString
    HString(const char *c){
        ch = nullptr;
        length = 0;
        //计算c字符串长度
        for(;c[length] != '\0';length++);
        //如果长度为0,则直接结束
        if(length == 0) return;
        //申请空间
        ch = (char*) malloc(length * sizeof (char));
        //按顺序填充数组
        int i = 0;
        for(;i<length;i++){
            ch[i] = c[i];
        }
        //设置字符串结束符
        ch[i] = '\0';
    }
};
 
int main() {
    HString* hString = new HString("123456");
    printf("%d\n",hString->length);
    printf("%s\n",hString->ch);
    return 0;
}

块链存储

如果字符串很长,以至于在逻辑地址空间上找不到一个足够长的连续空间来存放字符串,就会导致程序异常.块链存储的思想是把字符串切割为多个更小的子串分开存放,这样就可以充分利用内存中的碎片,只要内存足够,就不会出现无法分配的问题

在下面的代码中,我们以4个字符为一组切割字符串

//一个存储块存放4个字符
struct Block{
    char ch[4];
    Block* next;
};
 
class BString{
public:
    Block* head;
    //使用原有字符串构造HString
    BString(const char *c){
        //首块链地址
        head = (Block*) malloc(sizeof (Block));
        head->next = nullptr;
        //now表示当前操作的块链地址,初始值为首块链地址
        Block* now = head;
        int i=0;
        while(true){
            //将原字符串储存到块链中
            now->ch[i % 4] = c[i];
            //如果保存的字符是\0,则结束循环
            if(c[i] == '\0') break;
            //i后移一位
            ++i;
            //i是4的倍数,说明一个块链已经用完了
            if(i % 4 == 0){
                //申请新的块链
                Block* temp = (Block*)malloc(sizeof (Block));
                temp->next = nullptr;
                //当前块链的next指向新块链
                now->next = temp;
                //把now切换到新的块链
                now = temp;
            }
        }
    }
};
 
int main() {
    BString* bString = new BString("1234567890abcdefghijklmnopqrstuvwxyz");
    Block* block = bString->head;
    while (block != nullptr){
        for(char c : block->ch){
            if(c != '\0'){
                printf("%c",c);
            }else{
                break;
            }
        }
        block = block->next;
    }
    return 0;
}

模式匹配算法

算法思想

模式匹配是一个查找子串的过程

查找子串的思路是,将原字符串的第一个字符与子串的第一个字符相比较,如果相同,则比较原字符串和子串的第二个字符,否则将子串位置后移一位,比较原字符串的第二个字符与子串的第一个字符

这种方法有一个缺点,假设原字符串和子串如下

1 2	string ori = "1231234"; //原字符串 string sub = "1234"; //子串

当比较到第4个位置时,发现两者不同,于是子串后移一位

子串共移动了四次,并且每次都会从头开始比较,而实际上这是不必要的,因为我们知道子串的前三项互不相同,所以第二次和第三次移动是多余的

算法改进

假设子串为“ABABC”,当匹配到第4个字符“B”时发现不一致,这就说明前面3个字符一定是一致的,即原字符串的前4位可能是“ABAC”,所以我们知道原字符串的第3位一定是“A”,而子串的第1位也是“A”,那么就可以跳过这个“A”

跳过“A”的方法是将子串的指针直接向后移动,我们可以设置一个 next 数组,用来存放当前字符不匹配时,指针应该指向子串的第几个字符

i 表示原字符串内的指针,j 表示子串内的指针,i 和 j 同时从0开始递增,其中 i 会永远加下去,而 j 一旦遇到不同就会回退

以“ABABC”为例

next[0]=-1,因为子串的第一位就不匹配时,下次肯定是也是从子串的第一位开始匹配,并且原字符串的指针 i 也要跟着后移一位,-1用于标记这种情况,没有其它实际含义.下面的四种情况里,都是 j 在移动,而 i 不动.i 只在匹配到相同字符时才会后移一位
next[1]=0,因为子串的第二位不匹配时,说明原字符串是“A?”,要从第一位开始匹配,而原字符串的指针 i 不动
next[2]=0,因为子串的第三位不匹配时,说明原字符串是“AB?”,要从第一位开始匹配,同理 i 也是不动
next[3]=1,因为子串的第四位不匹配时,说明原字符串是“ABA?”,问号前面的字符“A”恰好是子串的第一个字符“A”,所以我们不需要再次比较,只需要比较子串的第二个字符
next[4]=2,因为子串的第五位不匹配时,说明原字符串是“ABAB?”,问号前面的两个字符“AB”恰好等于子串的开头两个字符“AB”,那么我们就不需要比较这两个字符,直接从子串的第三个开始

于是我们得到next数组: {-1,0,0,1,2}

下面编写查找该子串的代码

char ori[] = "ABABDBFABABABCCA";
char sub[] = "ABABC";
 
int* GetNext(char* str, int length){
    //仅针对于"ABABC"的情况
    return new int[]{-1,0,0,1,2};
}
 
int Search(char* ori, char* sub, int ori_len, int sub_len){
    int i = 0, j = 0;
    //获取next数组
    int* next = GetNext(sub, sub_len);
    //循环继续的条件是i和j都没有超出字符串长度
    while(i < ori_len && j < sub_len){
        if(j == -1 || ori[i] == sub[j]){
            //如果子串的第一个就不匹配(-1标记),那么i要后移一位,而j变成0
            //如果ori[i]和sub[j]相匹配,那么继续检查下一个,i和j都要后移
            //由于我们使用-1来标记第一种情况,所以只要++j就可以把j置零
            ++i;
            ++j;
        }else{
            //如果不匹配,则i不动,j移动到next数组指定的位置
            j = next[j];
        }
    }
    //如果结束循环时,j恰好等于子串的长度,说明j已经遍历完整个子串,
    //查找成功,返回子串在原字符串开始的位置,
    //否则查找失败,返回-1
    if(j == sub_len){
        return i - sub_len;
    }else{
        return -1;
    }
}
 
int main() {
    int ori_len = sizeof(ori) - 1;//原字符串长度
    int sub_len = sizeof(sub) - 1;//子串长度
    printf("%d", Search(ori,sub,ori_len,sub_len));
    return 0;
}

如果代码正确,那么应该会打印“9”

next数组

这个算法的关键在于next数组

同样以“ABABC”为例

next[0]=-1,理由与上面的一致
从字串的第二个开始,需要判断子串中是否存在相同子串,例如“ABABC”中就出现了两次完全一致的“AB”,那么下次“AB”出现时我们就知道要如何跳过了,假设子串的第5个字符“C”出现了不匹配,那么我们只需要把它指向“AB”第一次出现的位置的后一位,也就是 next[4]=2,这样下次就不用重复匹配“AB”字符了

由此我们发现计算next数组的关键在于寻找重复子串,而这实际上又是一个模式匹配过程,只不过并没有现成的子串给我们查找,而是需要我们自己发现子串,这个结论将会在下面用到

以“ABABC”为例,原字符串和子串都是“ABABC”,i 和 j 同时从 0 开始,如果ori[i] == sub[j],说明找到了某个相同子串

   i
   ⇓
ABABC
  ABABC
   ⇑
   j

那么我们就得到下面结论

1 2	//如果下一个字符不匹配,那么把它指向第一个重复子串的后一位 next[i+1] = j+1

同时我们还要把 i 和 j 后移一位,以继续匹配下一个字符

现在 i 和 j 都已经后移一位,我们遇到了下面的情况: ori[i] != sub[j]

    i
    ⇓
ABABC
  ABABC
    ⇑
    j

这时需要把 j 前移,重新开始比较前面的字符,但是要前移到哪个位置？

实际上,通过上述步骤,我们可以得到下面两个结论

1.模式匹配用到的的next数组仅和子串有关,与原字符串无关
2.计算next数组的过程也是一次模式匹配

得到第一个结论很方便,因为我们在分析“ABABC”的next数组时根本就没有用到原字符串,第二个结论上面已经做过解释

于是我们就得到另一个结论

当 ori[i] != sub[j] 时:

1	j = next[j]

我们在 ori[i-1] == sub[j-1] ,也就是上一步时,已经得到了 next[j] 的值,而next数组就是子串遇到不匹配时,j 应该指向的位置,所以我们可以直接使用

现在我们已经有了完整的计算next数组的函数

int* GetNext(char* str, int length){
    //申请next数组空间
    int* next = (int*)malloc(sizeof(int) * length);
    int i = 0, j = -1;
    //通过分析我们知道
    next[0] = -1;//与上文分析一致,-1仅仅是标记
    while(i < length){
        if(j == -1 || str[i] == str[j]){
            //i和j后移一位,并得到next数组的值
            ++i;
            ++j;
            next[i] = j;
        }else{
            //j前移到next指定的位置
            j = next[j];
        }
    }
    return next;
}

完整代码

如果程序正确,下面的代码将打印结果：30

int* GetNext(char* str, int length){
    //申请next数组空间
    int* next = (int*)malloc(sizeof(int) * length);
    int i = 0, j = -1;
    //通过分析我们知道
    next[0] = -1;//与上文分析一致,-1仅仅是标记
    while(i < length){
        if(j == -1 || str[i] == str[j]){
            //i和j后移一位,并得到next数组的值
            ++i;
            ++j;
            next[i] = j;
        }else{
            //j前移到next指定的位置
            j = next[j];
        }
    }
    return next;
}
 
int Search(char* ori, char* sub, int ori_len, int sub_len){
    int i = 0, j = 0;
    //获取next数组
    int* next = GetNext(sub, sub_len);
    //循环继续的条件是i和j都没有超出字符串长度
    while(i < ori_len && j < sub_len){
        if(j == -1 || ori[i] == sub[j]){
            //如果子串的第一个就不匹配(-1标记),那么i要后移一位,而j变成0
            //如果ori[i]和sub[j]相匹配,那么继续检查下一个,i和j都要后移
            //由于我们使用-1来标记第一种情况,所以只要++j就可以把j置零
            ++i;
            ++j;
        }else{
            //如果不匹配,则i不动,j移动到next数组指定的位置
            j = next[j];
        }
    }
    //如果结束循环时,j恰好等于子串的长度,说明j已经遍历完整个子串,
    //查找成功,返回子串在原字符串开始的位置,
    //否则查找失败,返回-1
    if(j == sub_len){
        return i - sub_len;
    }else{
        return -1;
    }
}
 
int main() {
    char ori[] = "HCABUDABCDAYABCDIASFNABCDSDIUAABCDEFA";
    char sub[] = "ABCDE";//该子串出现在ori[30]的位置
    int ori_len = sizeof(ori) - 1;//原字符串长度
    int sub_len = sizeof(sub) - 1;//子串长度
    printf("%d", Search(ori,sub,ori_len,sub_len));
    return 0;
}