串的朴素模式匹配算法，主要思想是对主串(S)的每一个字符作为

[单选题]

串的朴素模式匹配算法，主要思想是对主串(S)的每一个字符作为子串(T)开头，与要匹配的字符串进行匹配。主串(S)的长度为n，要匹配的子串的长度为m，那么朴素模式匹配算法的最坏时间复杂度为：

```
O((n-m)*m)
```
```
O((n＋1)*m)
```
```
O((n-m＋1)*m)
```
```
O((m＋1)*n)
```

查看正确选项

牛客992130223号

最好：O(1),第一次匹配就成功

最坏： O((n-m + 1 ) * m ),每次匹配度需要匹配m个长度(子串前面都成功，最后一个匹配完发现不成功)，需要匹配n-m + 1 次，这个此时子串末端已到主串末端了， n- m 是代表之前匹配的次数，+ 1 是最后一次的匹配

附上参考链接：https://zhuanlan.zhihu.com/p/24649304

发表于 2020-03-17 10:33:06 回复(0)

php小何

串的朴素模式匹配算法也称为BF(Brute-Force)算法，其基本思想是：从主串的第一个字符起与子串的第一个字符进行比较，若相等，则继续逐对字符进行后续的比较；若不相等，则从主串第二个字符起与子串的第一个字符重新比较，以此类推，直到子串中每个字符依次和主串中的一个连续的字符序列相等为止，此时称为匹配成功。如果不能在主串中找到与子串相同的字符序列，则匹配失败。BF算法是最原始、最暴力的求解过程，但也是其他匹配算法的基础。下面通过具体Demo演示该算法的基本思想。

发表于 2020-07-19 17:22:33 回复(0)