串的模式匹配(Brute-Force算法)

Published on:
Tags: 数据结构 串

算法介绍#

Brute-Force算法也称为简单匹配算法。B-F算法使用暴力枚举的方式，从目标串S中查找与模式串T一样的子串，若存在，则返回子串的开始位置，若不存在则返回-1.

  • 目标串：$S = s_1s_2s_3…s_n$
  • 模式串：$T = t_1t_2t_3…t_n$
  • 模式匹配：查找与模式串一样的子串的过程称为模式匹配
  • 目标串长度 $sLength$，模式串长度 $tLength$

算法匹配过程#

  1. 首先模式串T的长度必须小于等于目标串
  2. 模式匹配过程
  • 从目标串 $S$ 的第 $i$ 个位置开始寻找与模式串 $T$ 一样的子串 $( 0 <= i <= sLength-tLength)$
  • 遍历目标串 $S$ ，从 $i$ 到 $i+tLength$ 之间的字符，与模式串逐个比较
    • 若出现任意一个字符不相同，则跳出遍历，$i$ 向前移动一位，重新遍历目标串 $S$
    • 若每一个字符都相同，则返回 $i$

C代码#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>

int bf(char *s,char *t);

int main()
{
    char s[] = "[Done] exited with code=0 in 0.454 seconds";
    char t[] = "Done";
    int index = bf(&s[0],&t[0]);
    printf("index=%d\n",index);
    return 0;
}

int StrLength(char *s)
{
    int i = 0;
    while(*(s+i) != '\0')
        i++;
    
    return i;
}

//  Brute-Force算法 
int bf(char *s,char *t)
{
    int sLength = StrLength(s);
    int tLength = StrLength(t);
    if(sLength < tLength) return -1;
    int si = 0,ti = 0;
    while (si+tLength <= sLength)
    {
        int flag = 1;
        for(ti=0;ti<tLength;ti++)
            if(*(s+si+ti) != *(t+ti))
            {
                flag = 0;
                break;
            }

        if(flag)
            return si;
        else
        {
            ti = 0;
            si++;
        }
    }

    return -1;
}

时间复杂度#

情况 时间复杂度
最好情况： $O(tLength)$
最坏情况： $O(tLength*sLength)$