目录
在主串中找到与模式串相同的子串,并返回子串的位置。模式匹配在串处理系统中是最重要的操作之一。
主串的长度为m,子串的长度为n:将主串中所有长度为m的子串依次与模式串进行比较,直到找到一个完全匹配的子串或者所有的子串都不匹配为止,最多比较的次数为(m-n+1)。
主串:qinghuadaxuecomputervisionmydream
子串:vision
- #include
- #include
- #include
-
- #define maxn 100
-
- char S[maxn];
- char T[maxn];
-
-
- void substr(char *s,char r[maxn],int i,int n){
- int k=0;
- for(int j=i;j<(n+i);j++){
- r[k]=s[j];
- k++;
- }
- r[k]='\0';
- }
-
- //比较串是否相同
- bool Compare(char*s,char*t){
- int n=strlen(s);
- int m=strlen(t);
- for(int i=0;i
- if(s[i]!=t[i]){
- return false;
- }
- }
- return true;
- }
-
-
- //方法一
- int index_1(char*s,char*t,int m,int n){
- int pos=0;
- int len=m-n+1;
- while(pos<=len){
- char r[maxn];
- substr(s,r,pos,n);
- if(!Compare(r,t)){
- pos++;
- }else{
- return pos;
- }
- }
- return -1;
- }
- //方法二
- int index_2(char*s,char*t,int m,int n){
- int pos=0;
- int j=0,i=0;
- while(i
- if(s[i]==t[j]){
- i++;
- j++;
- }else{
- i=i-j+1;
- j=0;
- }
- }
- if(j>=n){
- return i-n;
- }else{
- return -1;
- }
- }
-
-
- int main(){
- printf("请输入主串: ");
- scanf("%s",&S);
- printf("\n");
- printf("请输入模式串: ");
- scanf("%s",&T);
- int m=strlen(S);
- int n=strlen(T);
- int pos=index_2(S,T,m,n);
- if(pos==-1){
- printf("匹配失败!\n");
- }else{
- printf("匹配成功!\n");
- printf("pos = %d\n",pos);
- }
- return 0;
- }
注:上面的程序每个子串都要进行比较m个字符,共n-m+1个子串,因此上面的时间复杂度最坏的情况下O((n-m+1)*m)≈O(n*m)(主串n>>模式串m).因此对其进行改进的算法KMP。
KMP算法是由D.E.Knuth,V.R.Pratt和J.H.Morris同时发现的,简称KMP算法。KMP算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。
思想:每当一趟匹配过程中出现字符比较不等时,不需要回溯i指针,而是利用已经得到的“部分匹配”的结果将模式向右滑动尽可能远的一段距离之后,继续进行比较。
怎么实现指针i不需要回溯呢?也就是当主串中第i个字符与模式中第j个字符“失配”时,主串中第i个字符(指针i不回溯)应与模式中哪个字符再比较?
j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
模式串 | a | b | a | a | b | c | a | c |
next[j] | 0 | 1 | 1 | 2 | 2 | 3 | 1 | 2 |
- void get_next(char*t,int next[maxn],int n){
- int i=0;
- int j=-1;
- next[i]=-1;
- while(i
- if(j==-1||t[i]==t[j]){
- i++;
- j++;
- next[i]=j;
- }else{
- j=next[j];
- }
- }
- }
- #include
- #include
- #include
-
- #define maxn 100
-
- char S[maxn];
- char T[maxn];
-
- void get_next(char*t,int next[maxn],int n){
- int i=0;
- int j=-1;
- next[i]=-1;
- while(i
- if(j==-1||t[i]==t[j]){
- i++;
- j++;
- next[i]=j;
- }else{
- j=next[j];
- }
- }
- }
- int index(char*s,char*t,int next[maxn],int m,int n){
- int pos=0;
- int j=0,i=0;
- while(i
- if(j==-1||s[i]==t[j]){
- i++;
- j++;
- }else{
- j=next[j];
- }
- }
- if(j>=n){
- return i-n;
- }else{
- return -1;
- }
- }
-
-
- int main(){
- int next[maxn];
- for(int i=0;i
- next[i]=0;
- }
- printf("请输入主串: ");
- scanf("%s",&S);
- printf("\n");
- printf("请输入模式串: ");
- scanf("%s",&T);
- int m=strlen(S);
- int n=strlen(T);
- //得到next函数
- get_next(T,next,n);
- //abaabac=>0 1 1 1 2 3 1
- printf("next = ");
- for(int i=0;i
- printf("%d\t",next[i]);
- }
- printf("\n");
- //匹配位置
- int pos=index(S,T,next,m,n);
- if(pos==-1){
- printf("匹配失败!\n");
- }else{
- printf("匹配成功!\n");
- printf("pos = %d\n",pos);
- }
- return 0;
- }
注:时间复杂度为O(n+m).
方法一:首先求解出next函数值,然后根据函数值求解nextval函数值:
j | 1 | 2 | 3 | 4 | 5 | 6 |
模式串 | a | b | a | b | a | a |
next[j] | 0 | 1 | 1 | 2 | 3 | 4 |
- //这里的char*t存储的字符是从1开始的
- void Get_nextval(char*t,int next,int nextval,int n){
- nextval[1]=0;
- for(int j=2;j<=n;j++){
- if(t[next[j]]==t[j]){
- nextval[j]=nextval[next[j]];
- }else{
- nextval[j]=next[j];
- }
- }
- }
j | 1 | 2 | 3 | 4 | 5 | 6 |
模式串 | a | b | a | b | a | a |
nextva;[j] | 0 | 0 | 0 | 1 | 0 | 4 |
方法二:直接使用下面的方法求解nextval函数值也可以
- void get_next(char*t,int next[maxn],int n){
- int i=0;
- int j=-1;
- nextval[i]=-1;
- while(i
- if(j==-1||t[i]==t[j]){
- i++;
- j++;
- if(t[i]!=t[j]){
- nextval[i]=j;
- }else{
- nextval[i]=nextval[j];
- }
- }else{
- j=next[j];
- }
- }
- }