中企动力网站策划,摄影作品集,嘉兴网站备案去哪里,杭州滨江网站制作目录 BF算法
KMP算法 BF算法
F算法#xff0c;即暴力(Brute Force)算法#xff0c;是普通的模式匹配算法#xff0c;BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配#xff0c;若相等#xff0c;则继续比较S的第二个字符和 T的第二个字符#xf…目录 BF算法
KMP算法 BF算法
F算法即暴力(Brute Force)算法是普通的模式匹配算法BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配若相等则继续比较S的第二个字符和 T的第二个字符若不相等则比较S的第二个字符和T的第一个字符依次比较下去直到得出最后的匹配结果。BF算法是一种蛮力算法。 ----这段话来自百度百科。 这段话晦涩难懂需要例子支持。下面我们就通过例子来解释这个问题。 假定我们给出字符串 ”ababcabcdabcde”作为主串 然后给出子串 ”abcd”,现在我们需要查找子串是否在主串中出现出现返回主串中的第一个匹配的下标失败返回-1 ; 只要在匹配的过程当中匹配失败那么i回退到刚刚位置的下一个,j回退到0下标重新开始。 对应C代码
/**
Author高博
Date2021-08-02 21:54
str:主串
sub:子串
*/
int BF(char *str,char *sub)
{
assert(str ! NULL sub ! NULL);
if(str NULL || sub NULL)
{
return -1;
}
int i 0;
int j 0;
int strLen strlen(str);
int subLen strlen(sub);
while(i strLen j subLen)
{
if(str[i] sub[j])
{
i;
j;
}
else
{
//回退
i i-j1;
j 0;
}
}
if(j subLen)
{
return i-j;
}
return -1;
}
int main()
{
printf(%d\n,BF(ababcabcdabcde,abcd));
printf(%d\n,BF(ababcabcdabcde,abcde));
printf(%d\n,BF(ababcabcdabcde,abcdef));
return 0;
} 对应java代码
/**
* Created by GAOBO
* Description:
* User: GAOBO
* Date: 2021-08-02
* Time: 22:05
*/
public class Test {
public static int BF(String str,String sub) {
if(str null || sub null) return -1;
int strLen str.length();
int subLen sub.length();
int i 0;
int j 0;
while (i strLen j subLen) {
if(str.charAt(i) sub.charAt(j)) {
i;
j;
}else {
i i-j1;
j 0;
}
}
if(j subLen) {
return i-j;
}
return -1;
}
public static void main(String[] args) {
System.out.println(BF(ababcabcdabcde,abcd));
System.out.println(BF(ababcabcdabcde,abcde));
System.out.println(BF(ababcabcdabcde,abcdef));
}
}
时间复杂度分析最坏为O(m*n); m是主串长度n是子串长度
KMP算法
KMP算法是一种改进的字符串匹配算法由D.E.KnuthJ.H.Morris和V.R.Pratt提出的因此人们称它为克努特—莫里斯—普拉特操作简称KMP算法。KMP算法的核心是利用匹配失败后的信息尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(mn) [1] 。 来自-------百度百科。区别KMP 和 BF 唯一不一样的地方在我主串的 i 并不会回退并且 j 也不会移动到 0 号位置 1 .首先举例为什么主串不回退 2 .j的回退位置 引出next数组 KMP 的精髓就是 next 数组也就是用 next[j] k;来表示不同的 j 来对应一个 K 值 这个 K 就是你将来要移动的 j要移动的位置。 而 K 的值是这样求的 1、规则找到匹配成功部分的两个相等的真子串不包含本身一个以下标 0 字符开始另一个以 j-1 下标字符结尾。 2、不管什么数据 next[0] -1;next[1] 0;在这里我们以下标来开始而说到的第几个第几个是从 1 开始 求next数组的练习 练习 1 举例对于”ababcabcdabcde” 求其的 next 数组 -1 0 0 1 2 0 1 2 0 0 1 2 0 0 练习 2 再对”abcabcabcabcdabcde ”,求其的 next 数组 -1 0 0 0 1 2 3 4 5 6 7 8 9 0 1 2 3 0 到这里大家对如何求next数组应该问题不大了接下来的问题就是已知next[i] k;怎么求next[i1] ?如果我们能够通过 next[i]的值,通过一系列转换得到 next[i1]得值那么我们就能够实现这部分。 那该怎么做呢 首先假设 next[i] k 成立那么就有这个式子成立 P0...Pk-1 Px...Pi-1;得到 P0...Pk-1 Pi-k..Pi-1;到这一步我们再假设如果 Pk Pi;我们可以得到 P0...Pk Pi-k..Pi;那这个就是 next[i1] k1; 那么 Pk ! Pi 呢 看如下实例 c语言代码
void GetNext(int *next,const char *sub)
{
int lensub strlen(sub);
next[0] -1;
next[1] 0;
int i 2;//下一项
int k 0;//前一项的K
while(i lensub)//next数组还没有遍历完
{
if((k -1) || sub[k] sub[i-1])//
{
next[i] k1;
i;
k;//k k1???//下一个K的值新的K值
}
else
{
k next[k];
}
}
}
int KMP(const char *s,const char *sub,int pos)
{
int i pos;
int j 0;
int lens strlen(s);
int lensub strlen(sub);
int *next (int *)malloc(lensub*sizeof(int));//和子串一样长assert(next ! NULL);
GetNext(next,sub);
while(i lens j lensub)
{
if((j -1) || (s[i] sub[j]))
{
i;
j;
}
else
{
j next[j];
}
}
free(next);
if(j lensub)
{
return i-j;
}
else
{
return -1;
}
}
int main()
{
char *str ababcabcdabcde;
char *sub abcd;
printf(%d\n,KMP(str,sub,0));
return 0;
}
java算法代码
public static void getNext(int[] next, String sub){
next[0] -1;
next[1] 0;
int i 2;//下一项
int k 0;//前一项的K
while(i sub.length()){//next数组还没有遍历完
if((k -1) || sub.charAt(k) sub.charAt(i-1)) {
next[i] k1;
i;
k;
}else{
k next[k];
}
}
}
public static int KMP(String s,String sub,int pos) {
int i pos;
int j 0;
int lens s.length();
int lensub sub.length();
int[] next new int[sub.length()];
getNext(next,sub);
while(i lens j lensub){
if((j -1) || (s.charAt(i) sub.charAt(j))){
i;
j;
}else{
j next[j];
}
}
if(j lensub) {
return i-j;
}else {
return -1;
}
}
public static void main(String[] args) {
System.out.println(KMP(ababcabcdabcde,abcd,0));
System.out.println(KMP(ababcabcdabcde,abcde,0));
System.out.println(KMP(ababcabcdabcde,abcdef,0));
}
next数组的优化 next 数组的优化即如何得到 nextval 数组有如下串 aaaaaaaab,他的 next 数组是-1,0,1,2,3,4,5,6,7.而修正后的数组 nextval 是 -1 -1 -1 -1 -1 -1 -1 -1 7。为什么出现修正后的数组假设在 5 号处失败了那退一步还是a还是相等接着退还是 a。 练习模式串 t‘abcaabbcabcaabdab’ 该模式串的 next 数组的值为 D nextval 数组的值为 F。 A 0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B 0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2 C 0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 E 0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F 0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1
