扩展KMP算法(Extend KMP) 学习小记 Hdu 4333 Revolving Digits

水深无声 2022-08-27 09:50 194阅读 0赞

前几天复习了KMP，现在来学习exKMP。

exKMP的作用是：求出一个串所有后缀串(即s\[i...len\])和模式串的最长公共前缀。

网上学习资料版本不多，看来看去还是 刘雅琼 的PPT 《扩展的KMP算法》 最好理解。

这里有一个字符串算法大集合：字符串：[KMP Eentend-Kmp 自动机 trie图 trie树 后缀树 后缀数组 - 星星的日志][KMP Eentend-Kmp _ trie_ trie_ _ _ -]

**Hdu 4333 Revolving Digits**

题意：给出一个不含前导0的数字，每一次把它的最后一位移动到最前面，一直持续下去，分别求形成的数字小于，等于和大于原来数的个数。

例如：134可以形成134，341，413三个数，所以分别是1，1，1。

如果移动过程中出现前导0，则去掉前导0，并认为形成了新的数字。

以下分析和代码参考了kuangbin大神的：http://www.cnblogs.com/kuangbin/archive/2012/11/09/2763242.html

扩展KMP能求出一个串所有后缀串(即s\[i...len\])和模式串的最长公共前缀。于是只要将这个串复制一遍，求出该串每个后缀与其本身的最长公共前缀即可，当公共前缀>=len时，显然相等，否则只要比较下一位就能确定这个串与原串的大小关系。  
  
至于重复串的问题，只有当这个串有循环节的时候才会产生重复串，用KMP的next数组求出最小循环节，用长度除以最小循环节得到循环节个数，在将3个答案都除以循环节个数即可。

#include <cstdio>
    #include <cstring>
    
    const int N=2000010;
    #define max(a,b) ((a)>(b)?(a):(b))
    
    int next[N];  // next[i]表示T[i..m]与T的最长公共前缀长度
    int extend[N];// extend[i]表示S[i..n]与T的最长公共前缀长度
    
    void exKMP (char s[],char t[]) //s为主串，t为模板串
    {
    	int i,j=0,p,L;
    	int lens=strlen(s);
    	int lent=strlen(t);
    	next[0]=lent;
    	
    	while (j+1<lent && t[j]==t[j+1])
    		j++;
    	next[1]=j;
    	
    	int a=1;
    	for (i=2;i<lent;i++)
    	{
    		p=next[a]+a-1;
    		L=next[i-a];
    		if (i+L<p+1) next[i]=L;
    		else
    		{
    			j=max(0,p-i+1);
    			while (i+j<lent && t[i+j]==t[j])
    				j++;
    			next[i]=j;
    			a=i;
    		}
    	}
    
    	j=0;
    	while (j<lens && j<lent && s[j]==t[j])
    		j++;
    	extend[0]=j;
    	a=0;
    	for (i=1;i<lens;i++)
    	{
    		p=extend[a]+a-1;
    		L=next[i-a];
    		if (L+i<p+1) extend[i]=L;
    		else
    		{
    			j=max(0,p-i+1);
    			while (i+j<lens && j<lent && s[i+j]==t[j])
    				j++;
    			extend[i]=j;
    			a=i;
    		}
    	}
    }
    
    void Cal_next (const char *pattern,int len)  //改进写法,next[]有多个-1  
    {  
        int i=0,j=-1;  
        next[0]=-1;  
        while (i<len)  
        {  
            while (j>=0 && pattern[i]!=pattern[j])  
                j=next[j];  
            j++,i++;  
            if (pattern[j]==pattern[i])  
                next[i]=next[j];  
            else  
                next[i]=j;  
        }  
    }
    
    char source[N],after[N];
    
    int main ()
    {
    	int T;
    	scanf("%d",&T);
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    		scanf("%s",source);
    		int len=strlen(source);
    		strcpy(after,source);
    		strcat(after,source);
    		exKMP(after,source);
    		int cnt1=0,cnt2=0,cnt3=0;
    
    		for (int i=0;i<len;i++)
    			if (extend[i]>=len) cnt2++;
    			else
    			{
    				if (after[i+extend[i]]<source[extend[i]]) cnt1++;
    				else cnt3++;
    			}
    
    		Cal_next(source,len);
    		int t=len-next[len];
    		int tol=1;
    		if (len%t==0) tol=len/t;
    		printf("Case %d: %d %d %d\n",Cas,cnt1/tol,cnt2/tol,cnt3/tol);
    	}
    	return 0;
    }

[KMP Eentend-Kmp _ trie_ trie_ _ _ -]: http://duanple.blog.163.com/blog/static/709717672009825004092/