HDU-4333-Revolving Digits(扩展KMP)

CSDN

题目链接

题意：

给你一个字符串，你可以将该字符串的任意长度后缀截取下来然后接到最前面，让你统计所有新串中有多少种字典序小于、等于、大于原串。

题解：

首先我们将原串扩展成两倍，算一遍扩展KMP（自匹配），时间复杂度O(n)。这样一来，我们就得到了eKMP[i]，eKMP[i]代表s[i…len-1]与s的最长公共子串。为了避免重复子串重复计数，我们先求出s的最小循环节：然后我们只需统计最小循环节以内的字符就可。当eKMP[i]>=len时，显然是原串，E++;否则我们只需比较一位就可判断大小，即：比较s[i+eKMP[i]]和s[eKMP[i]]的大小。为什么只需比较一位?因为s[0…eKMP[i]-1]和s[i…i+eKMP[i]-1]是相同的，只需判断第一个不相同的位置就可

代码：

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100010;//字符串长度最大值
int next1[maxn*2],ex[maxn];//ex数组即为extend数组
char s[maxn*2],s2[maxn];
int n;
//预处理计算next数组
void getnext(){
	int i=0,j,po,len=strlen(s);
	next1[0]=len;//初始化next[0]
	while(s[i]==s[i+1]&&s[i+1])//计算next[1]
	i++;
	next1[1]=i;
	po=1;//初始化po的位置
	for(i=2;i<len;i++){
		if(next1[i-po]+i<=next1[po]+po-1)//第一种情况，可以直接得到next[i]的值
		next1[i]=next1[i-po];
		else //第二种情况，要继续匹配才能得到next[i]的值
		{
			j=next1[po]+po-i;
			if(j<0)j=0;//如果i>po+next[po],则要从头开始匹配
			while(i+j<len&&s[j]==s[j+i])//计算next[i]
			j++;
			next1[i]=j;
			po=i;//更新po的位置
		}
	}
}
void work(){
	int ret1,ret2,ret3;
	ret1=ret2=ret3=0;
	//for(int i=0;i<2*n;i++)printf("%d ",next1[i]);
	//cout<<endl;
	for(int i=0;i<n;i++){
		if(i!=0&&next1[i]>=n)break;
		if(next1[i]<n){
			if(s[i+next1[i]]<s[next1[i]])ret1++;
			else ret3++;
		}else ret2++;
	}
	printf("%d %d %d\n",ret1,ret2,ret3);
}
int main(){
	int t,cas=0;
	scanf("%d",&t);
	while(t--){
		scanf("%s",s);
		n=strlen(s);
		printf("Case %d: ",++cas);
		for(int i=0;i<n;i++){
			s[n+i]=s[i];
		}s[2*n]='\0';
		//printf("\n%s",s);
		getnext();
		work();
	}
}