bf算法和kmp算法混合代码

Sure! Here's an example of a code snippet that combines the Boyer-Moore and Knuth-Morris-Pratt algorithms for string searching:

def preprocess_pattern(pattern):
    pattern_length = len(pattern)
    border = [0] * (pattern_length + 1)
    i, j = 0, -1
    border[i = j

    while i < pattern_length:
        while j >= 0 and pattern[i != pattern[j]:
            j = border[j]
        i += 1
        j +=1
        border[i] = j

    return border

def bm_kmp_search(text, pattern):
    text_length = len(text)
    pattern_length = len(pattern)
    border = preprocess_pattern(pattern)

    occurrences = []

    i, j = 0, 0
    while i

相关问题

bf算法和kmp算法代码

BF算法和KMP算法都是字符串匹配算法，用于在一个主串中查找一个子串是否存在。BF算法的思想是暴力匹配，即从主串的第一个字符开始，依次和子串的每一个字符进行比较，如果匹配失败，则主串和子串都需要回溯，直到找到匹配的子串或者主串遍历完毕。KMP算法则是通过预处理子串的信息，来避免在匹配过程中的回溯，从而提高匹配效率。

下面是BF算法和KMP算法的代码：

BF算法：

bool BF(char a[],char b[]){
    int index1 = 0;//指向a的头部
    int index2 = 0;//指向b的头部
    for(int i = 0;i<strlen(a);i++){//轮数
        if(a[index1]==b[index2]){
            index1++;
            index2++;
        }else{
            index1 = i+1;
            index2 = 0;
        }
        if(index2==strlen(b))
            return true;
    }
    return false;
}

int main(){
    char a[6] = {'a','c','a','b','d','a'};
    char b[3] = {'a','b','d'};
    char c[3] = {'a','b','e'};
    if(BF(a,b))
        printf("匹配\n");
    else
        printf("不匹配\n");
    if(BF(a,c))
        printf("匹配\n");
    else
        printf("不匹配\n");
    return 0;
}

KMP算法：

void getNext(char* p, int* next) {
    int pLen = strlen(p);
    int k = -1;
    int j = 0;
    next[0] = -1;
    while (j < pLen - 1) {
        if (k == -1 || p[j] == p[k]) {
            ++k;
            ++j;
            next[j] = k;
        }
        else {
            k = next[k];
        }
    }
}

bool KMP(char* s, char* p) {
    int sLen = strlen(s);
    int pLen = strlen(p);
    int i = 0;
    int j = 0;
    int next[pLen];
    getNext(p, next);
    while (i < sLen && j < pLen) {
        if (j == -1 || s[i] == p[j]) {
            ++i;
            ++j;
        }
        else {
            j = next[j];
        }
    }
    if (j == pLen) {
        return true;
    }
    else {
        return false;
    }
}

int main() {
    char s[] = "ababcabcacbab";
    char p[] = "abcac";
    if (KMP(s, p)) {
        printf("匹配\n");
    }
    else {
        printf("不匹配\n");
    }
    return 0;
}

bf算法和kmp算法

BF算法和KMP算法都是用于字符串匹配的算法，但它们在时间复杂度和实际应用中有所不同。

BF算法的时间复杂度是O(mn)，其中m是主串的长度，n是子串的长度。在BF算法中，每次遇到不匹配的字符时，主串的下一字符会重新开始与子串的第一个字符比较，这样的操作效率相对较低。

相比之下，KMP算法的时间复杂度是O(m+n)。KMP算法采用了一种最长公共前后缀的计算方法，通过预处理模式串，避免了不必要的回溯操作，提高了匹配效率。当不匹配时，KMP算法会根据预处理的信息跳过一些字符，避免无效的比较，从而减少了比较次数。

因此，KMP算法相对于BF算法来说更为高效。在实际应用中，一般会优先选择KMP算法来进行字符串匹配，以提高匹配效率。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [BF算法与KMP算法](https://blog.csdn.net/zhangfei5354/article/details/89667505)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]