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();}
}