拓展KMP模板

博主CSDN

• 扩展KMP
• next[i]表示为模式串S2中以i为起点的后缀字符串和模式串S2的最长公共前缀长度.
• extend[i]表示为以字符串S1中以i为起点的后缀字符串和模式串S2的最长公共前缀长度.

  #include<bits/stdc++.h>
  using namespace std;
  const int maxn=100010;//字符串长度最大值 
  int next[maxn],ex[maxn];//ex数组即为extend数组
  char s[maxn],s2[maxn];
  int n;
  //预处理计算next数组
  void getnext(){
  	int i=0,j,po,len=strlen(s);
  	next[0]=len;//初始化next[0]
  	while(s[i]==s[i+1]&&i+1<len)//计算next[1]
  	i++;
  	next[1]=i;
  	po=1;//初始化po的位置 
  	for(i=2;i<len;i++){
  		if(next[i-po]+i<next[po]+po)//第一种情况，可以直接得到next[i]的值
  		next[i]=next[i-po];
  		else //第二种情况，要继续匹配才能得到next[i]的值 
  		{
  			j=next[po]+po-i;
  			if(j<0)j=0;//如果i>po+next[po],则要从头开始匹配
  			while(i+j<len&&s[j]==s[j+i])//计算next[i]
  			j++;
  			next[i]=j;
  			po=i;//更新po的位置 
  		} 
  	} 
  } 
  //计算extend数组
  void extend(){
  	int i=0,j,po,len=strlen(s),l2=strlen(s2);
  	getnext();//计算子串的next数组
  	while(s[i]==s2[i]&&i<len)i++;
  	ex[0]=i;
  	po=0;//初始化po的位置
  	for(i=1;i<len;i++){
  		if(next[i-po]+i<ex[po]+po)
  		ex[i]=next[i-po];//第一种情况
  		else{
  			j=ex[po]+po-i;
  			if(j<0)j=0;//如果j>ex[po]+po则从头开始匹配
  			while(i+j<len&&j<<l2&&s[j+i]==s2[j])//计算ex[i]
  			j++;
  			ex[i]=j;
  			po=i; 
  		} 
  	} 
  	
  }
  int main(){
  
  }