实现BF字符串匹配算法完整版

BF算法，也称为朴素字符串匹配算法，是一种简单直观的字符串匹配算法。它的基本思想是，从主串的第一个字符开始，依次比较主串和模式串中的每一个字符，如果出现不匹配的情况，则将主串的指针向后移动一位，重新从主串的下一个字符开始匹配。这个过程一直持续到模式串匹配完整个主串，或者在匹配过程中发现了不匹配的情况，此时匹配失败。

下面是BF算法的完整实现代码：

int BF(char* s, char* p) {
    int i = 0, j = 0;
    int s_len = strlen(s);
    int p_len = strlen(p);
    while (i < s_len && j < p_len) {
        if (s[i] == p[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }
    if (j == p_len) {
        return i - j;
    } else {
        return -1;
    }
}

其中，s表示主串，p表示模式串。函数返回值为模式串在主串中第一次出现的位置，如果没有出现则返回-1。

相关问题

bf字符串匹配Python代码实现 代码分析

BF (Boyer-Moore) 字符串匹配算法是一种高效的文本搜索算法，它通过预处理模式串（即待查找的子串），避免在不匹配的情况下在主串中回溯。下面是使用 Python 实现的 Boyer-Moore 算法的一个简单版本：

def bad_char_search(pattern, text):
    m = len(pattern)
    n = len(text)
    lps =  * m  # longest proper prefix suffix (LPSPS)

    for i in range(1, m):
        j = lps[i - 1]
        while j > 0 and pattern[j] != pattern[i]:
            j = lps[j - 1]
        if pattern[j] == pattern[i]:
            j += 1
        lps[i] = j

    i = 0
    while i < n:
        j = m - 1
        while j >= 0 and text[i + j] == pattern[j]:
            j -= 1
        if j < 0:
            print(f"Pattern found at index {i}")
            i += m
        else:
            i += lps[j + 1]

# 示例用法
pattern = "ABCD"
text = "ADAMABCDAB"
bad_char_search(pattern, text)

代码分析：
1. 首先初始化两个指针，`m` 表示模式串长度，`n` 表示主串长度。`lps` 数组用于存储模式串的后缀和前缀公共部分的信息。

2. 计算 Look-Aside-Table (LPS)。这个循环计算了 LPS 列表，使得 `lps[i]` 表示以模式串第 `i+1` 个字符结尾的最长前缀，该前缀也出现在模式串中。

3. `while` 循环内，找到 `pattern[i]` 在 `pattern[j]` 后面的位置 `j`，更新 `lps[i]`。

4. 主循环中，从主串的开始处开始匹配。如果找到一个匹配，`j < 0`，则找到了模式串，输出索引并向前移动 `m` 个字符继续搜索。否则，根据 `lps[j + 1]` 值向右移动。

5. 递归调用 `bad_char_search`，直到遍历完整个主串。

一、 用BF算法实现模式串匹配。 要求：使用定长顺序存储，返回模式串在目标串中的位置。 目标串：abcabebfschaglwke 模式串：bfscha

在使用Brute Force (BF) 算法，也称为朴素匹配或简单匹配，来实现模式串在目标串中的位置查找时，不需要预先构建任何数据结构，而是直接逐个字符地比较。以下是基本步骤：

1. **初始化**：从目标串的第一个字符开始（索引为0），模式串的起始位置设为0。

2. **循环遍历**：每次将模式串向右移动一位（索引加1），直到模式串遍历完或找到匹配的子串。

a. 比较目标串的当前字符和模式串的当前字符是否相等。

b. 如果相等，继续比较下一个目标字符；如果不等，则回到目标串的前一个字符，让模式串重新开始匹配。

3. **匹配成功**：如果模式串完全匹配到目标串的一部分（即模式串等于剩余的目标串），则返回模式串在目标串中的起始位置。这里是0，因为模式串本身就是连续的。

4. **处理边界情况**：如果模式串遍历完了，而目标串还有剩余字符，说明没有找到匹配，返回-1表示未找到。

对于给定的例子，目标串为 "abcabebfschaglwke"，模式串为 "bfscha"。由于模式串在目标串的第5位开始，可以完整匹配一次，所以返回值为5。如果你需要具体的代码实现，下面是一个简单的Python版本：

def brute_force_match(target, pattern):
    target_len = len(target)
    pattern_len = len(pattern)

    for i in range(target_len - pattern_len + 1):
        if target[i:i+pattern_len] == pattern:
            return i

    return -1

target = "abcabebfschaglwke"
pattern = "bfscha"
print(brute_force_match(target, pattern))  # 输出：5