字符串采用顺序存储结构，设计求子串的算法

1. 首先输入原字符串和子串，确定它们的长度。
2. 从原字符串的第一个字符开始，依次比较原字符串和子串的每个字符是否相等。
3. 如果相等，则继续比较下一个字符，直到子串的最后一个字符。
4. 如果子串的所有字符都与原字符串中的一段连续字符相等，则找到了子串，返回该子串在原字符串中的起始位置。
5. 如果子串的某个字符与原字符串中的某个字符不相等，则从原字符串的下一个字符开始重新比较，直到找到子串或者原字符串遍历完毕。
6. 如果原字符串遍历完毕仍未找到子串，则说明原字符串中不存在该子串。

相关问题

字符串采用顺序存储结构，设计求子串的算法；

假设原字符串为str，子串为substr，其长度为len_sub。

1. 首先判断substr的长度是否小于等于str的长度，如果不是，则不存在子串，直接返回空。

2. 然后从str的第一个字符开始遍历，以当前字符作为子串的起始字符，判断接下来的len_sub个字符是否与substr相同。

3. 如果相同，则找到了一个子串，记录其起始位置并将其存入结果数组中。

4. 如果不同，则继续遍历str的下一个字符，以此类推直到遍历完整个字符串。

5. 最后返回结果数组，即为所有子串的起始位置。

代码实现如下：

vector<int> findSubstr(string str, string substr) {
    vector<int> res;
    int len_str = str.length(), len_sub = substr.length();
    if (len_sub > len_str) return res;
    for (int i = 0; i <= len_str - len_sub; i++) {
        bool flag = true;
        for (int j = 0; j < len_sub; j++) {
            if (str[i+j] != substr[j]) {
                flag = false;
                break;
            }
        }
        if (flag) res.push_back(i);
    }
    return res;
}

（一）字符串采用链式存储结构，设计求子串的算法； （二）字符串采用链式存储结构，设计删除子串的算法； （三）字符串采用顺序存储结构，设计模式匹配的BF算法。用C语言编写

（一）对于字符串采用链式存储结构，求子串的算法可以使用KMP（Knuth-Morris-Pratt）搜索算法。它是一种高效的字符串匹配算法，通过预处理模式串构建部分匹配表，避免了回溯过程。以下是C语言版本的大致步骤：

void getSubstr(char* str, char* pattern) {
    // KMP表的构建
    int lps[pattern_length];
    buildLPS(pattern, lps);

    int i = 0, j = 0;
    while (i < strlen(str)) {
        if (pattern[j] == str[i]) {
            i++;
            j++;
        } else if (j != 0) {
            j = lps[j - 1]; // 如果当前字符不匹配，从lps表回退
        } else {
            i++; // 如果模式串的第一个字符也不匹配，直接移动到下一个字符
        }
        if (j == pattern_length) { // 子串找到
            printf("子串 '%s' 在原串中第一次出现的位置: %d\n", pattern, i - j);
            j = lps[j - 1]; // 回溯到最后一个匹配字符
        }
    }
}

// 构建部分匹配表
int buildLPS(char* pat, int lps[]) {
    int len = 0, i;
    lps[0] = 0;
    for (i = 1; i < strlen(pat); i++) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
        } else {
            if (len != 0)
                len = lps[len - 1];
            else
                lps[i] = 0;
        }
    }
    return len;
}