（一）数据结构-串-朴素模式匹配-KMP模式匹配-KMP模式匹配优化

悠悠 2022-08-28 04:53 179阅读 0赞

话不多说，直接上代码，具体注释在代码里  
但是有几个概念需要注意  
1.主串：S=“google”  
2.子串：主串S中的某一连续的一部分  
3.模式串：一个想要在主串S中寻找到相同部分地串，可以不存在  
具体思想就不说了，这个代码是能成功运行的。

#include<stdio.h>
    #include<iostream>
    #include<string.h>
    #include<stdlib.h>
    
    using namespace std;
    
    #define MAXLEN 255
    
    typedef struct{ 		//线性表的存储结构，ch[0]空出来不用 
    	char ch[MAXLEN];	//存储字符
    	int length;		//记录当前有多少个数据
    }SString;
    
    void InputStr(SString &S)	//已完成 
    { 
    	//输入串 
    	int n;
    	cout<<"请输入字符串的字符个数：";
    	cin>>n;
    	int i;
    	for(i=1;i<=n;i++)
    	{ 
    		cin>>S.ch[i];
    	}
    	S.length = n;
    }
    
    void PrintStr(SString S)	//已完成 
    { 
    	//输出串 
    	for(int i=1;i<=S.length;i++)
    	{ 
    		cout<<S.ch[i];
    	}
    	cout<<endl;
    }
    
    bool SubString(SString &Sub, SString S, int pos, int len)	//已完成 
    { 
    	//寻找字串
    	if(pos+len-1>S.length)	//如果所在位置超出主串范围，返回false
    	{ 
    		return false;	
    	}
    	int k=1;
    	for(int i=pos;i<=pos+len-1;i++)		//暴力匹配
    	{ 
    		Sub.ch[k++] = S.ch[i];
    	}
    	Sub.length = k-1;
    	return true;
    }
    
    int Index(SString S, SString T)	//已完成 
    { 
    	//定位操作，将S中与T串相同的第一个字串的位置下标返回
    	int k=1;
    	int i=k;
    	int j=1;
    	while(i<=S.length && j<=T.length)
    	{ 
    		if(S.ch[i] == T.ch[j])
    		{ 
    			i++;
    			j++;
    		}
    		else
    		{ 
    			k++;
    			i=k;
    			j=1;
    		}
    	} 
    	if(j>T.length)
    	{ 
    		return k;
    	}
    	else
    	{ 
    		return 0;
    	}
    } 
    
    int StrCompare(SString S, SString T)	//已完成 
    { 
    	//字典序比较字符串大小
    	for(int i=1; i<=S.length && i<=T.length; i++)
    	{ 
    		if(S.ch[i] != T.ch[i])
    		{ 
    			return S.ch[i] - T.ch[i];
    		}
    	}
    	return S.length-T.length;
    }
    
    void Find_Next(SString T, int next[])	//已完成 
    { 
    	//寻找next数组
    	next[1] = 0;
    	next[2] = 1;
    	int i,j;
    	for(i=3;i<=T.length;i++)//goog
    	{ 
    		int max=0;
    		SString Sub;
    		SubString(Sub, T, 1, i-1);//取从1~i-1的字符串
    		for(j=1;j<Sub.length;j++)
    		{ 
    			SString Sub_left;
    			SString Sub_right;
    			SubString(Sub_left, Sub, 1, j);
    			SubString(Sub_right, Sub, Sub.length-j+1, j);
    			
    			if(StrCompare(Sub_left, Sub_right) == 0)
    			{ 
    				max = Sub_left.length;
    			} 
    		}
    		next[i] = max + 1;
    	}
    }
    
    int KMP_Index(SString S, SString T)		//已完成 
    { 
    	//KMP算法
    	int next[MAXLEN];
    	Find_Next(T, next);
    	int i=1;
    	int j=1;
    	while(i<=S.length && j<=T.length)
    	{ 
    		if(j==0 || (S.ch[i] == T.ch[j]))
    		{ 
    			i++;
    			j++;
    		}
    		else
    		{ 
    			j = next[j];
    		}
    	}
    	if(j>T.length) 
    	{ 
    		return i-T.length;
    	}
    	else
    	{ 
    		return 0;
    	}
    }
    
    void Find_Nextval(SString T, int next[], int nextval[])		//已完成 
    { 
    	//根据next数组寻找nextval数组
    	for(int i=1;i<=T.length;i++)
    	{ 
    		if(T.ch[i] == T.ch[next[i]])
    		{ 
    			nextval[i] = next[next[i]];
    		}
    		else
    		{ 
    			nextval[i] = next[i];
    		}
    	}
    }
    
    int KMP_Index_optimize(SString S, SString T)		//已完成 
    { 
    	//KMP算法的优化
    	int next[MAXLEN];
    	int nextval[MAXLEN];
    	Find_Next(T, next);
    	Find_Nextval(T, next, nextval);
    	int i=1;
    	int j=1;
    	while(i<=S.length && j<=T.length)
    	{ 
    		if(j==0 || (S.ch[i] == T.ch[j]))
    		{ 
    			i++;
    			j++;
    		}
    		else
    		{ 
    			j = nextval[j];
    		}
    	}
    	if(j>T.length) 
    	{ 
    		return i-T.length;
    	}
    	else
    	{ 
    		return 0;
    	}
    }
    //123456
    //google
    //011121
    //011021
    
    int main()
    { 
    	SString S;
    	InputStr(S);
    	SString T;
    	InputStr(T);
    	cout<<KMP_Index_optimize(S, T);
    
    	return 0;
    }