字符串匹配算法

文章目录

• • 字符串匹配算法
  • • 朴素匹配算法Brute-Force
    • hash Rabin-Karp匹配法
    • KMP算法
    • Sunday算法
    • SHIFT-AND算法

朴素匹配算法Brute-Force

时间复杂度O(N*M)

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

int brute_force(const char *s, const char *t) {
    for (int i = 0; s[i]; i++) {
        int flag = 0;
        for (int j = 0; t[j]; j++) {
            if (s[i + j] == t[j]) continue;
            flag = 1;
            break;
        }
        if (flag == 0) return i;
    }
    return -1;
}

int main() {
    
    char s[100], t[100];
    scanf("%s%s", s, t);
    printf("%d\n", brute_force(s, t));
    
    return 0;
}

hash Rabin-Karp匹配法

对母串的每一个字串进行hash n-m+1次hash hash(A) = hash(B) A=B

hash 的方法 abc = a * 26 * 26 + b * 26 + c

前一个：aeca hash(A) 后一个：ecae hash(B) hash(B) = hash(A) - (a * 26 * 26 * 26) + e

推导公式 h[i] = (h[i - 1] - 26 ^ (m - 1) * s[i - 1]) * 26 + s[i + m - 1]

问题：
1、hash值超过了int范围？

优化hash函数, 把字符与素数做映射, 而不是简单的a->1, b->2

优化hash函数, 更改hash策略, 直接把对应位置想加, 不做乘法法

2、hash冲突？ 发送冲突，则直接对比 （子字符串）

时间复杂度：
最好：O(N)
最坏：O(N*M) (发送哈希冲突次数过多)

KMP算法

母串S

模式串T

一、关键点：求模式串 的每一个前缀的子前缀的相等的最长前缀和后缀

x!=y: 对比x和z

abcdab

二、最长前缀后缀预处理

i = j 扩大 Sa 和 Sb，

i != j 利用sa和sb的最长前缀和后缀，再对比 i 和 j

如：模式串T abcxabcab

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

int next[100];

int kmp(const char *s, const char *t) { //s为母串， t为子串
	
    //init next
	next[0] = -1; //第一个字符的前后缀无意义
    
    for(int i = 0, j = -1; t[i]; i++) { //最长前缀后缀预处理
        while(j != -1 && t[j + 1] != t[i]) { //j!= -1 跳过第一个  t[j + 1] != t[i]第二种情况
            j = next[j]; //利用sa和sb的最长前缀和后缀，再对比	i 和 j + 1
        }
        if (t[j + 1] == t[i]) { // t[j + 1] == t[i]   扩大 Sa 和 Sb
            j++;
        }
        next[i] = j;  //存 当前最长值
    }    
    
    /*
	for (int i = 0; i < 20; i++) { //next[i] 默认-1，加一即为真实值
        printf("%d ", next[i]);
    }
    printf("\n");
    */
    
    //match string
    for(int i = 0, j = -1; s[i]; i++) {
        while(j != -1 && s[i] != t[j + 1]) {
            j = next[j];
        }
        if (s[i] == t[j + 1]) j++;
        if (t[j + 1] == '\0') return i - j; //返回位置
    }
    return -1;

}

int main() {
    char s[100], t[100];
    scanf("%s%s", s, t);
    kmp(s, t)；
    printf("%d\n", kmp(s, t));
    
    return 0;
}

无注释版

int next[100];

int kmp(const char *s, const char *t) {
    // init next
    next[0] = -1;
    for(int i = 1, j = -1; t[i]; i++) {
        while(j != -1 && t[j + 1] != t[i]) { j = next[j]; }
        if(t[j + 1] == t[i]) { j++; }
        next[i] = j;
    }
    // match string
    for(int i = 0, j = -1; s[i]; i++) {
        while(j != -1 && s[i] != t[j + 1]) { j = next[j]; }
        if(s[i] == t[j + 1]) j++;
        if(t[j + 1] == '\0') return i - j;
    } 
    return -1;
}

kmp 流式算法
a.out < input 512MB的内存处理10GB

hash算法
BM算法
Sunday算法

Sunday算法

1. SUNDAY 算法理解的核心，在于理解对齐点位
2. 是文本串的匹配尾部，一定会出现在模式串中的字符
3. 文本串应该和模式串中最后一位(从后往前找的第一位)出现该字符的位置对齐
4. 第一步：预处理**每一个字符（所有）**在模式串中最后一次出现的位置
5. 第二步：模拟暴力匹配算法过程，失配的时候，文本串指针根据预处理信息向后移动若干位

int sunday(const char *s, const char *t) {
    int len_s = strlen(s), len_t = strlen(t);
    int ind[256];
    
    //第一步：预处理每一个字符（所有 256个字符）在模式串中最后一次出现的位置
    for (int i = 0; i < 256; i++) ind[i] = len_t + 1;
    for (int i = 0; t[i]; i++) {
        ind[t[i]] = len _t - i;
    }
    
    int i = 0;
    while (i + len_t <= len_s) {
        int flag = 1;
        for (int j = 0; t[j]; j++) {
            if (s[i + j] == t[j]) continue;
            flag = 0;
            break;
        }
        if (flag == 1) return i; // 找到了匹配, 直接返回位置
        i += ind[s[i + len_t]]; // 匹配不成功, 找对齐点位, 出现在第几位, 就往后移动多少位置
    }
    return -1;
}

SHIFT-AND算法

模式串T转换为二维数组

d[a] = int(001001) 反过来

P = （P << 1 | 1) & d[s[i]]

P & (1 << (n - 1))

SHIFT-AND算法

1. 第一步对模式串做特殊处理，把每一种字符出现的位置，转换成相应的二进制编码

2. 后续匹配的过程中跟模式串一毛钱关系都没有

3. P的结构定义:
   相应的位置为1,意味着当前文本串后缀能匹配到模式串的第几位前缀

4. P的结构操作:
   文本串进来一个,对于每个p为1的地方,都有可能移动1位(都有可能多匹配一个字符),并且第一位O也有可能变成1,我们先假设,所有的1都能匹配得到假设完之后,开始验证我们的假设

时间复杂度 O(n+m)

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

int shift_and(const char *s, const char *t) {
    int code[256] = {0};
    int n = 0;
    for(int i = 0; t[i]; i++, n++) {
        code[t[i]] |= (1 << i); //t[i]  位置 加上 第i位的1
    }
    int p = 0;
    for(int i = 0; s[i]; i++) {
        p = (p << 1 | 1) & code[s[i]];
        if(p & (1 << (n - 1))) return i - n + 1; // 和t的n个前缀相等则完成字符串匹配
    }
    return -1;
}

int main() {
    
    char s[100], t[100];
    scanf("%s%s", s, t);
    printf("%d\n", shift_and(s, t));
    
    return 0;
}