bf算法求子串jing在主串beijing中的位置测试主串查找起始位置分别为1和5的情况的c语言代码

BFS (宽度优先搜索)通常用于图论中的遍历，而在字符串匹配中，我们更常使用KMP算法、Boyer-Moore算法或Rabin-Karp算法来寻找子串。不过，如果你想模拟简单的线性搜索（顺序查找），可以分别从起始位置1和5开始寻找子串"jing"在"beijing"中的位置。以下是C语言的一个简单实现：

#include <stdio.h>
#include <string.h>

// 从起始位置i开始搜索"jing"
int search(char str[], char sub[], int i) {
    int j = 0; // 子串的指针
    while (i < strlen(str) && j < strlen(sub)) {
        if (str[i] == sub[j]) { // 相等则继续
            i++;
            j++;
        } else {
            // 如果不相等，回退到最长公共前后缀的位置并检查下一个字符
            if (j != 0) {
                j = kmpBacktrack(sub, j);
            } else {
                i++; // 无匹配，直接向前移动主串指针
            }
        }
    }
    // 如果找到子串，则返回子串起始位置；否则返回-1
    return j == strlen(sub) ? i - j : -1;
}

// KMP的辅助函数，计算最长公共前后缀长度
int kmpBacktrack(char *sub, int j) {
    int len = 0;
    int lps[] = {0}; // 预处理后的LPS数组

    // 计算LPS数组
    for (int i = 1; i < strlen(sub); i++) {
        if (sub[i] == sub[len]) {
            len++;
            lps[i] = len;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
            }
        }
    }

    // 使用LPS数组回退
    while (lps[j] != 0) {
        j++;
    }
    return j;
}

int main() {
    char mainStr[] = "beijing";
    char subStr[] = "jing";

    printf("Search starting at position 1: %d\n", search(mainStr, subStr, 1));
    printf("Search starting at position 5: %d\n", search(mainStr, subStr, 5));

    return 0;
}

在这个代码中，`search`函数会尝试从给定的起始位置开始查找子串。请注意，这个实现不是最优的，因为它是线性的，对于大字符串效率较低。实际应用中，我们会选择更适合的算法如KMP算法。