HDU 4333 Revolving Digits 扩展KMP

本文主要是介绍HDU 4333 Revolving Digits 扩展KMP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目来源：HDU 4333 Revolving Digits

题意：求一个数字循环移动后有多少个不同的小于 等于 大于的数字

思路：扩展KMP求出S[i..j]等于S[0..j-i]的最长前缀 判断 next[i] 大于等于n就是相同 小于n判断S[next[i]]和S[next[i]+i]的大小

next数组的含义就是S字符串以i开始的和S本身(以0开始)的最长公共前缀 把题目输入的复制一倍 然后直接判断next数组 比较大小就行了

#include <cstdio>
#include <cstring>
using namespace std;const int maxn = 200010;
int f[maxn];
char a[maxn];void getFail(char* s)
{int n = strlen(s);int p = 0, k = 1;for(int i = 0; i+1 < n && s[i] == s[i+1]; i++)p++;f[0] = n;	f[1] = p;for(int i = 2; i < n/2; i++){int p = f[k]+k-1;int l = f[i-k];if(i+l-1 < p)f[i] = l;else{int j = p-i+1;if(j < 0)j = 0;while(i+j < n*2 && s[i+j] == s[j])j++;f[i] = j;k = i;}}
}
int main()
{int cas = 1;int T;scanf("%d", &T);while(T--){scanf("%s", a);int n = strlen(a);for(int i = 0; i < n; i++){a[i+n] = a[i];}a[2*n] = 0;getFail(a);int len;for(len = 1; len <= n; len++){if(f[len]+len >= n){if(n%len)len = n;break;}}int sum1 = 0, sum2 = 0, sum3 = 0;for(int i = 0; i < len; i++){if(f[i] >= n)sum2++;else if(a[i+f[i]] > a[f[i]])sum3++;elsesum1++;}printf("Case %d: %d %d %d\n", cas++, sum1, sum2, sum3);}return 0;
}

 

这篇关于HDU 4333 Revolving Digits 扩展KMP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---