考研数据结构串的模式匹配算法|BF和KMP算法分析及代码实现-一一网

这是我参与8月更文挑战的第4天，活动详情查看：8月更文挑战

考研数据结构串的模式匹配算法

串的模式匹配

模式匹配（Pattern Matching）：即子串定位运算（lndex（S;T）函数）

算法目的

确定主串S中所含子串T第一次出现的位置

初始条件

串S和T存在，T是非空串

操作结果

若主串S存在和串T值相同的子串，则返回它在主串S中第一次出现的位
置，否则返回0。

1 .经典模式匹配算法（BF算法）

BF算法设计思想

1.将主串S的第i个（初始i=l）字符和模式T的第1个字符进行比较，若相等，继续逐个比较后续字符；若不等，从主串S的下一字符（i++）起，重新与T的第一个字符进行比较。
2.直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T 匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值0.

#include<iostream>
#include<stdlib.h>
using namespace std;
//1.串的变长存储 
typedef struct HString{
	char *ch;
	int length;
}HString; 

//2.BF算法 
int BruteForce(HString str,HString substr){
	int i=1,j=1,k=i;
	while(i<=str.length&&j<=substr.length){
		if(str.ch[i] == substr.ch[j]){
			i++;
			j++;
		}
		else{
			j = 1;
			i = ++k;
		}
	}
	if(j>substr.length)
		return k;
	else
		return 0; 
}


int main(){
	return 0;
} 
复制代码

经典模式匹配算法(BF算法)
设主串长m,子串长n,则最坏情况时间复杂度：O((n-l) * (m-n))=O(n*m)
缺点：每次不匹配时，主串i指针与子串的j指针都要回退，使得算法效率低下。

2.KMP算法

特点：选次不匹配时主串指针i不回退，仅回退子串j指针到指定位置，且这个位置未必是子串串首。
KMP算法的核心就是计算j指针处出现不匹配时要回退的这个位置
不妨用next[]数组存储要求的位置信息,其中next[k]处存储的是当 j=k时发生不匹配时j应该回退的位置。
求解next[]数组只和字串有关，和主串无关

如何求解next[]数组？

手工求解思路：

next[l]=0 表第一个字符匹配失败，提示主串i后移
next[2]=1 表第二个字符匹配失败，此时子串j只能回退串首
next[j]的值为FL或FR的串长+1
FL或FR应尽可能取最大
求解next[]实际是在找最大前缀后缀公共元素长度

算法思路：

问题描述：

若已知next[k]=j时，如何求 next [k+1] ?

若 T[k]=T[j]，则next[k+l] = next[k]+l=j+l ,然后 k++,j++。
若 T[k]≠T[j],回退j 到 next[j],若j=O ，则重新判断T[k]与T[j],若j=0,则 next[k+l] = 1;

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define MaxSize 100
/*构造match数组*/
void BuildMatch(char *pattern,int *match)
{
  int n = strlen(pattern);
  int dis = 1,s = 0;
  while (s+dis < n)
  {
    if(pattern[s] == pattern[s+dis])
    {
      match[s+dis] = match[s+dis-1]+1;
      s++;
    }
    else
    {s = 0;dis++;}
  }
}
/*KMP*/
int KMP(char *str,char *pattern)
{
  int n = strlen(str);
  int m = strlen(pattern);
  int s = 0,p = 0;
  int *match = (int*)malloc(sizeof(int)*m);
 
  memset(match,-1,sizeof(int)*n);
  BuildMatch(pattern,match);
 
  while (s < n && p < m)
  {
    if(str[s] == pattern[p]){s++;p++;}
    else if(p > 0)p = match[p-1]+1;
    else s++;
  }
  return p == m ? s-m+1: -1;
}
int main(int argc, char const *argv[]) {
  char str[MaxSize],pattern[MaxSize];
  printf("请输入字符串:\n");
  scanf("%s",str);
  printf("请输入子串:\n");
  scanf("%s",pattern);
 
  int result = KMP(str,pattern);
  if(result == -1)printf("查找失败\n");
  else printf("首字母位置为:%d\n",result);
  return 0;
}
复制代码