本文主要是介绍HDU 5442 Favorite Donut 最大表示法+KMP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
首先2次最大表示法求出顺序和逆序情况下的位置，不过逆序求出来的是最大的下标，可以利用循环节来推出最小的位置。#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000010;
int f[maxn];
char s[maxn];
void getFail(char p[])
{
int m = strlen(p);
f[0] = f[1] = 0;
for(int i = 1; i < m; i++)
{
int j = f[i];
while(j && p[i] != p[j])
j = f[j];
f[i+1] = p[i] == p[j] ? j+1 : 0;
}
}
int min_exp(char str[])
{
int i = 0, j = 1, len, k = 0;
len = strlen(str);
while(i < len && j < len && k < len)
{
int t = str[(i+k)%len] - str[(j+k)%len];
if(!t)
k++;
else
{
if(t > 0)
i = i + k + 1;
else
j = j + k + 1;
if(i == j)
j++;
k = 0;
}
}
return i > j ? j : i;
}
int max_exp(char str[])
{
int i = 0, j = 1, len, k = 0;
len = strlen(str);
while(i < len && j < len && k < len)
{
int t = str[(i+k)%len] - str[(j+k)%len];
if(!t)
k++;
else
{
if(t < 0)
i = i + k + 1;
else
j = j + k + 1;
if(i == j)
j++;
k = 0;
}
}
return i > j ? j : i;
}
char s1[22222], s2[22222];
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
int len;
scanf("%d %s", &len, s);
getFail(s);
int l = len-f[len];
int p1 = max_exp(s);
for(int i = p1, j = 0; j < len; j++, i = (i+1)%len)
{
s1[j] = s[i];
}
s1[len] = 0;
reverse(s, s+len);
int p2 = max_exp(s);
for(int i = p2, j = 0; j < len; j++, i = (i+1)%len)
{
s2[j] = s[i];
}
s2[len] = 0;
int ans = len%l == 0 ? l : len;
p2 = len-p2-1;
int dir = 0;
p1 %= ans;
p2 %= ans;
if(strcmp(s1, s2) < 0 || strcmp(s1, s2) == 0 && p1 > p2)
{
p1 = p2;
dir = 1;
}
printf("%d %d\n", p1+1, dir);
}
return 0;
}这篇关于HDU 5442 Favorite Donut 最大表示法+KMP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
