C++串的常用操作以及朴素匹配算法

﹏ヽ暗。殇╰゛Y 2023-10-11 17:54 45阅读 0赞

#### 串的定义 ####

串，即字符串，用单引号或双引号表示的一组字符序列  
子串包含于主串。  
对串的主要操作如下：  
1.获取某个子串在主串中的起始位置  
2.获取主串的长度  
3.获取从第index位置开始的字符后的子串位置  
4.复制主串  
5.赋值字串  
6.比较两个字串的大小

串的两种实现方法：
        顺序方式实现（静态存储和动态存储），链式方式实现(这种方式实现的串需要用malloc函数申请存储空间，同时在销毁时，调用free函数)

#### 串的操作 ####

*  定义  
    这里注意，结构体中的str字符数组是从1开始存字符的。

typedef struct {
        
        int length;//表示串的长度
        char str[MAXSIZE];//静态字符数组，存储串，可采用废弃第一个字符位置，这样为了保持在查找某一处字串时能够和其在主串的位置匹配
    } String;
    
    void initString(String &s) {
        
        s.length = 0;
    }

*  比较大小

//两个字符串比较大小，每个位置一个字符一个字符的比较，如果两个字符不一致，则返回 s1[i] - s2[i] 即可 ， 减号做ASCII码的运算。
    //如果以较小的字符比较完了，还没有比较出来谁大谁小，则直接返回s1.length - s2.length即可，也就是说，长度长的那个大
    //如果返回正数，s1比s2大，0 s1等于s2，小于0则s1小于s2
    int compare(String s1, String s2) {
        //TODO 由于字符串是从char数组下标1开始，所以一定注意：在比较字符串时，从下标1开始获取字符一个一个比较
        for (int i = 1; i <= s1.length && i <= s2.length; ++i) {
        
            char s1str = s1.str[i];
            char s2str = s2.str[i];
            if (s1str != s2str) {
        
                return s1str - s2str;
            }
        }
        return s1.length - s2.length;
    }

*  获取某个子串在主串中的起始位置  
    这里注意，在取主串中某几个连续字符与字串比较时，字串的下标时固定的，例如字串的长度是3，那么字串的下标就是固定的1,2,3.

//获取字串s2在主串s1的起始位置，如果未找到，则返回0
    int indexOf(String s1, String s2) {
        
        if (s2.length > s1.length) {
        
            return 0;
        }
        int s2Len = s2.length;//获取s2的长度
        printf(" %d \n", s2Len );
        for (int i = 1; i <= s1.length; ++i) {
        
            //判断从i处位置加上s2Len长度的字符是否等于s1在i到i+s2Len处的子串
            int size = i + s2Len;
            if (size > s1.length) {
        
                printf(" %s \n", "444" );
                return 0;//如果超过了主串的长度，则说明主串剩余的长度小于子串的长度，则返回0
            }
    //        printf(" %c%c%c , %c%c%c  \n", s1.str[i], );
            bool equals = true;
            int s2Index = 1;
            for (int j = i; j < size; j++) {
        
                //依次取出主串和子在j处的字符进行比较，有一个不符合，则i++，全部符合则返回当前i的值
                char s1Char = s1.str[j];
                char s2Char = s2.str[s2Index];
                if ((s1Char - s2Char) != 0) {
        
                    //不匹配
                    equals = false;
                    break;
                }
                s2Index++;
            }
            if (equals) {
        
                return i;
            }
        }
        return 0;
    }

*  追加字符串

//追加str，也可以看作赋值操作
    void appendStr(String &s, char *str) {
        
        for (int i = 0; str[i] != '\0'; i++) {
        
            s.str[++s.length] = str[i];
        }
    }

*  获取某个主串从第i处开始的后j的字符

//获取某个字符串的子串
    String getSubString(String s,int start,int length){
        
        String substring;
        initString(substring);
        if(start + length > s.length ){
        
            return substring;
        }
        for (int i = start; i < start + length; ++i) {
        
            //赋值字符串
            substring.str[++substring.length] = s.str[i];
        }
        return substring;
    }

#### 完整使用示例 ####

#include "stdio.h"
    #include "malloc.h"
    #include <stdlib.h>
    
    #define MAXSIZE 255
    
    /**
        串，即字符串，用单引号或双引号表示的一组字符序列
        子串包含于主串。
        对串的主要操作如下：
            1.获取某个子串在主串中的起始位置
            2.获取主串的长度
            3.获取从第index位置开始的字符后的子串位置
            4.复制主串
            5.赋值字串
            6.比较两个字串的大小
    
         串的两种实现方法：
            顺序方式实现（静态存储和动态存储），链式方式实现(这种方式实现的串需要用malloc函数申请存储空间，同时在销毁时，调用free函数)
     */
    
    typedef struct {
        
        int length;//表示串的长度
        char str[MAXSIZE];//静态字符数组，存储串，可采用废弃第一个字符位置，这样为了保持在查找某一处字串时能够和其在主串的位置匹配
    } String;
    
    void initString(String &s) {
        
        s.length = 0;
    }
    
    //追加str，也可以看作赋值操作
    void appendStr(String &s, char *str) {
        
        for (int i = 0; str[i] != '\0'; i++) {
        
            s.str[++s.length] = str[i];
        }
    }
    
    //两个字符串比较大小，每个位置一个字符一个字符的比较，如果两个字符不一致，则返回 s1[i] - s2[i] 即可 ， 减号做ASCII码的运算。
    //如果以较小的字符比较完了，还没有比较出来谁大谁小，则直接返回s1.length - s2.length即可，也就是说，长度长的那个大
    //如果返回正数，s1比s2大，0 s1等于s2，小于0则s1小于s2
    int compare(String s1, String s2) {
        //TODO 由于字符串是从char数组下标1开始，所以一定注意：在比较字符串时，从下标1开始获取字符一个一个比较
        for (int i = 1; i <= s1.length && i <= s2.length; ++i) {
        
            char s1str = s1.str[i];
            char s2str = s2.str[i];
            if (s1str != s2str) {
        
                return s1str - s2str;
            }
        }
        return s1.length - s2.length;
    }
    
    //获取字串s2在主串s1的起始位置，如果未找到，则返回0
    int indexOf(String s1, String s2) {
        
        if (s2.length > s1.length) {
        
            return 0;
        }
        int s2Len = s2.length;//获取s2的长度
        printf(" %d \n", s2Len );
        for (int i = 1; i <= s1.length; ++i) {
        
            //判断从i处位置加上s2Len长度的字符是否等于s1在i到i+s2Len处的子串
            int size = i + s2Len;
            if (size > s1.length) {
        
                printf(" %s \n", "444" );
                return 0;//如果超过了主串的长度，则说明主串剩余的长度小于子串的长度，则返回0
            }
    //        printf(" %c%c%c , %c%c%c  \n", s1.str[i], );
            bool equals = true;
            int s2Index = 1;
            for (int j = i; j < size; j++) {
        
                //依次取出主串和子在j处的字符进行比较，有一个不符合，则i++，全部符合则返回当前i的值
                char s1Char = s1.str[j];
                char s2Char = s2.str[s2Index];
                if ((s1Char - s2Char) != 0) {
        
                    //不匹配
                    equals = false;
                    break;
                }
                s2Index++;
            }
            if (equals) {
        
                return i;
            }
        }
        return 0;
    }
    
    //获取某个字符串的子串
    String getSubString(String s,int start,int length){
        
        String substring;
        initString(substring);
        if(start + length > s.length ){
        
            return substring;
        }
        for (int i = start; i < start + length; ++i) {
        
            //赋值字符串
            substring.str[++substring.length] = s.str[i];
        }
        return substring;
    }
    
    int main() {
        
    
        //定义字符串s1
        String s1;
        //初始化字符串s1
        initString(s1);
        //定义字符串s2
        String s2;
        //初始化字符串s2
        initString(s2);
    
        //s1追加字符串
        char s1str[] = "hello world abc 111 723";
        appendStr(s1, s1str);
        printf(" %s \n", s1.str );
    
        //s2追加字符串
        char s2str[] = "hello world abc 111 8";
        appendStr(s2, s2str);
    
        //判断字符串是否为空
        printf(" s1 is Empty  %d \n", s1.length == 0);
        printf(" s2 is Empty  %d \n", s2.length == 0);
    
        //比较两个字符串的大小
        printf(" s1 compare s2  %d \n", compare(s1, s2));
    
        //获取某个子串在字符串中的首次出现的首字符的位置
        //定义一个字串
        char s3str[] = "abc";
        String s3;
        initString(s3);
        //追加字符串
        appendStr(s3, s3str);
        int index = indexOf(s1, s3); //获取子串s3在主串s1处的位置
        printf(" first index position :  %d \n", index);
    
        //获取某个字符串从第i处位置开始的后j个子串
        String substring = getSubString(s1,3,5);//获取s1从第三个字符位置开始的后5个字符
        for (int i = 1; i <= substring.length; ++i) {
        
            printf("%c", substring.str[i] );
        }
    
        return 0;
    }

#### 串匹配算法 ####

*  朴素模式匹配算法

在长度为n的主串，长度为m的子串最多有 n-m+1个，最坏的时间复杂度为o(nm),最坏的情况无非就是遍历到最后一个子串时才和模式串匹配，那么此时相当于遍历了 （n-m+1）次，而每次又循环匹配了m次，所以此时的时间复杂度就是 (n-m+1)\*m =  
nm - m2 + m = O(nm),为什么最后等于nm，因为 通常主串的长度是远远大于模式串的。

朴素算法完整实现如下：

#include "stdio.h"
    #include "malloc.h"
    #include <stdlib.h>
    
    #define MAXSIZE 255
    
    /**
        串，即字符串，用单引号或双引号表示的一组字符序列
        子串包含于主串。
        对串的主要操作如下：
            1.获取某个子串在主串中的起始位置
            2.获取主串的长度
            3.获取从第index位置开始的字符后的子串位置
            4.复制主串
            5.赋值字串
            6.比较两个字串的大小
    
         串的两种实现方法：
            顺序方式实现（静态存储和动态存储），链式方式实现(这种方式实现的串需要用malloc函数申请存储空间，同时在销毁时，调用free函数)
     */
    
    typedef struct {
        
        int length;//表示串的长度
        char str[MAXSIZE];//静态字符数组，存储串，可采用废弃第一个字符位置，这样为了保持在查找某一处字串时能够和其在主串的位置匹配
    } String;
    
    void initString(String &s) {
        
        s.length = 0;
    }
    
    //追加str，也可以看作赋值操作
    void appendStr(String &s, char *str) {
        
        for (int i = 0; str[i] != '\0'; i++) {
        
            s.str[++s.length] = str[i];
        }
    }
    
    //两个字符串比较大小，每个位置一个字符一个字符的比较，如果两个字符不一致，则返回 s1[i] - s2[i] 即可 ， 减号做ASCII码的运算。
    //如果以较小的字符比较完了，还没有比较出来谁大谁小，则直接返回s1.length - s2.length即可，也就是说，长度长的那个大
    //如果返回正数，s1比s2大，0 s1等于s2，小于0则s1小于s2
    int compare(String s1, String s2) {
        //TODO 由于字符串是从char数组下标1开始，所以一定注意：在比较字符串时，从下标1开始获取字符一个一个比较
        for (int i = 1; i <= s1.length && i <= s2.length; ++i) {
        
            char s1str = s1.str[i];
            char s2str = s2.str[i];
            if (s1str != s2str) {
        
                return s1str - s2str;
            }
        }
        return s1.length - s2.length;
    }
    
    //获取字串s2在主串s1的起始位置，如果未找到，则返回0
    int indexOf(String s1, String s2) {
        
        if (s2.length > s1.length) {
        
            return 0;
        }
        int s2Len = s2.length;//获取s2的长度
        printf(" %d \n", s2Len);
        for (int i = 1; i <= s1.length; ++i) {
        
            //判断从i处位置加上s2Len长度的字符是否等于s1在i到i+s2Len处的子串
            int size = i + s2Len;
            if (size > s1.length) {
        
                printf(" %s \n", "444");
                return 0;//如果超过了主串的长度，则说明主串剩余的长度小于子串的长度，则返回0
            }
    //        printf(" %c%c%c , %c%c%c  \n", s1.str[i], );
            bool equals = true;
            int s2Index = 1;
            for (int j = i; j < size; j++) {
        
                //依次取出主串和子在j处的字符进行比较，有一个不符合，则i++，全部符合则返回当前i的值
                char s1Char = s1.str[j];
                char s2Char = s2.str[s2Index];
                if ((s1Char - s2Char) != 0) {
        
                    //不匹配
                    equals = false;
                    break;
                }
                s2Index++;
            }
            if (equals) {
        
                return i;
            }
        }
        return 0;
    }
    
    //获取某个字符串的字串
    String getSubString(String s, int start, int length) {
        
        String substring;
        initString(substring);
        if (start + length > s.length) {
        
            return substring;
        }
        for (int i = start; i < start + length; ++i) {
        
            //赋值字符串
            substring.str[++substring.length] = s.str[i];
        }
        return substring;
    }
    
    //朴素模式匹配算法
    int puSuIndexOf(String s1, String s2) {
        
        int s1Len = s1.length;
        int s2Len = s2.length;
        if (s2.length > s1.length) {
        
            return 0;//未找到
        }
        //长度为n的主串最多包含长度为m的主串有 (n-m) + 1 个
        int totalSubString = s1Len - s2Len + 1;
        int i = 1;
        while (i <= totalSubString) {
        
            //获取主串中从i位置开始后的s2Len个元素
            String substr = getSubString(s1, i, s2Len);
            int result = compare(s2, substr);//模式串和子串进行比较
            if (result == 0) {
        
                return i;
            } else {
        
                i++;
            }
        }
        return 0;
    }
    
    int main() {
        
    
        //定义字符串s1
        String s1;
        //初始化字符串s1
        initString(s1);
        //定义字符串s2
        String s2;
        //初始化字符串s2
        initString(s2);
    
        //s1追加字符串
        char s1str[] = "hello world abc 111 723";
        appendStr(s1, s1str);
    
        //s2追加字符串
        char s2str[] = "abc";
        appendStr(s2, s2str);
    
        //朴素模式匹配算法模式串
        int index = puSuIndexOf(s, s2);
        printf(" %d \n", index);
        return 0;
    }