Top

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]是相同的,只需判断第一个不相同的位置就可

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#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();
}
}
文章版权为Anoyer博客所有,转载请以链接形式标明本文地址