hdu 3374 String Problem(KMP+字符串最小最大表示)

迈不过友情╰ 2021-11-16 09:54 185阅读 0赞

题意：给定一个字符串，计算它的最小最大表示开始出现的位置及次数。

思路：最小最大表示模板……然后利用KMP算法next数组的性质求循环节出现的次数，原理见博客内相关博文

#include <iostream>
    #include <cstdio>
    #include <string>
    using namespace std;
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    
    char str[1000000+5];
    int next[1000000+5];
    
    /*
    用最小表示法求字符串S的最小字典序
    返回字典序最小的串的首字母位置
    */
    int minstr (char s[])
    {
    	int len=strlen(s);
    	int i=0,j=1;
    	while(i<=len-1 && j<=len-1)
    	{
    		int k=0;
    		while(k<=len-1 && s[(i+k)%len]==s[(j+k)%len])
    			k++;
    		if(k>=len)
    			break;
    		if(s[(i+k)%len]>s[(j+k)%len])
    			i=max(i+k+1,j+1);
    		else
    			j=max(j+k+1,i+1);
    	}
    	return min(i,j);
    }
    /*
    用最大表示法求字符串S的最大字典序
    返回字典序最大的串的首字母位置
    */
    int maxstr (char s[])
    {
    	int len=strlen(s);
    	int i=0,j=1;
    	while(i<=len-1 && j<=len-1)
    	{
    		int k=0;
    		while(k<=len-1 && s[(i+k)%len]==s[(j+k)%len])
    				k++;
    		if(k>=len)
    			break;
    		if(s[(i+k)%len]<s[(j+k)%len])
    			i=max(i+k+1,j+1);
    		else
    			j=max(j+k+1,i+1);
    	}
    	return min(i,j);
    }
    
    void Get_next ()  //next[]只有第一个是-1  
    {  
        int j=0,k=-1;  
        next[0]=-1;  
        while (str[j])  
            if (k==-1 || str[j] == str[k])  
            {  
                j++;  
                k++;  
                next[j]=k;  
            }  
            else k=next[k];  
    }
    
    int main()
    {
    	while (~scanf("%s",str))
    	{
    		int maxn=maxstr(str);
    		int minn=minstr(str);
    		Get_next ();
    		int len=strlen(str);
    		int t=len % (len-next[len]);
    		int ans=t?1:len / (len-next[len]);
    		printf("%d %d %d %d\n",minn+1,ans,maxn+1,ans);
    	}
    	return 0;
    }