hnuun 11544 小明的烦恼——找字符串(求环形字符串的最小最大字典序)
2024-08-30 19:11:02
http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11544&courseid=0
最小最大表示法:
求环形字符串的最小最大字典序:
参考:http://www.cnblogs.com/ziyi--caolu/p/3245132.html
最小表示法:
初始时,i=0,j=1,分别以i,j,为起始点顺着i,j,往下比较直到找的str[i+k]!=str[j+k],然后分两种情况考虑:
1、 str[i+k]>str[j+k],i变成i=i+k+1,j不变,然后继续往下比较。
2、 str[i+k]<str[j+k],j变成j=j+k+1,i不变,然后继续往下比较。
直到i或j大于串长,找较小者。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
#include <map>
#include <queue>
#pragma comment(linker, "/STACK:102400000,102400000")
#define CL(arr, val) memset(arr, val, sizeof(arr)) #define ll long long
#define inf 0x7f7f7f7f
#define lc l,m,rt<<1
#define rc m + 1,r,rt<<1|1
#define pi acos(-1.0) #define L(x) (x) << 1
#define R(x) (x) << 1 | 1
#define MID(l, r) (l + r) >> 1
#define Min(x, y) (x) < (y) ? (x) : (y)
#define Max(x, y) (x) < (y) ? (y) : (x)
#define E(x) (1 << (x))
#define iabs(x) (x) < 0 ? -(x) : (x)
#define OUT(x) printf("%I64d\n", x)
#define lowbit(x) (x)&(-x)
#define Read() freopen("a.txt", "r", stdin)
#define Write() freopen("b.txt", "w", stdout);
#define maxn 1010
#define maxv 1010
#define mod 1000000000
using namespace std;
char str[];
int work(int m)
{
int i,j,l;
i=; j=;
while(i<m && j<m)
{
for(l=;l<m;l++)
if(str[(i+l)%m]!=str[(j+l)%m]) break;
if(l>m) break;
if(str[(i+l)%m] > str[(j+l)%m])
i=i+l+;
else
j=j+l+;
if(i==j) j=i+;
}
if(i<j) return i;
return j;
} int main()
{
//freopen("a.txt","r",stdin);
int t;
scanf("%d",&t);
while(t--)
{
scanf("%s",str);
// printf("%s\n",str);
int l=strlen(str);
printf("%d\n",work(l));
}
return ;
}
最大表示法:
int work(int len,char pat[]) //最大表示法
{
//int len = strlen(pat);
int i=,j=,k=;
while(i<len && j<len && k<len)
{
int t = pat[(i+k)%len] - pat[(j+k)%len];
if(!t) k++;
else
{
if(t>) j = j+k+;
else i = i+k+;
if(i == j) j++;
k = ;
}
}
return i<j?i:j;
}
最新文章
- Hibernate 系列 06 - 对象在JVM中的生命周期
- LeetCode题目按公司分类
- 51nod p1201 整数划分
- 第9章 用内核对象进行线程同步(1)_事件对象(Event)
- Touch Event
- Unity shader(CG) 写一个 散色、折射、反射、菲涅尔、gamma、简单后期屏幕特效
- php 未配置curl
- Create STATISTICS,UPDATE STATISTICS
- 08 Linux下MySQL的下载、安装及启动
- hibernate不关闭session后果
- mysql管理员操作
- c语言趣味
- Spring在Web项目中的三种启动加载的配置
- 实习生的Django[1]
- 管理工具 Kafka Manager
- 单应性(homography)变换的推导
- mybatis 一对多和多对一关联查询
- js时间戳与日期格式的相互转换
- qt creator 中的";提升为...";功能简介
- 201621123050 《Java程序设计》第9周学习总结