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

假设原字符串为S，子串为T，S的长度为n，T的长度为m。

1. 遍历S的每一个字符，从第一个字符开始，对于每个字符i，都与T的第一个字符j进行比较。

2. 如果S中的字符i与T中的字符j相等，则从i+1和j+1开始继续比较下一个字符，直到T中的所有字符都比较完毕。

3. 如果在比较过程中发现有字符不相等，则继续遍历S的下一个字符i+1，并重复步骤2。

4. 如果在比较过程中T中的所有字符都已经比较完毕，且都相等，则找到了子串，返回子串在S中的起始位置i-m+1。

5. 如果遍历完S中的所有字符，仍然没有找到子串，则返回-1，表示没有找到。

算法时间复杂度为O(n*m)，空间复杂度为O(1)。

相关问题

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

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

（一）字符串采用链式存储结构，设计求子串的算法； （二）字符串采用链式存储结构，设计删除子串的算法； （三）字符串采用顺序存储结构，设计模式匹配的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;
}