HDU3374 字符串最大最小表示法模板
2024-10-07 23:51:57
一开始没太看懂什么意思,拿笔反复推了一遍才大概知道最大最小表示法是怎么求的,感觉太神奇了...
#include <iostream>
#include <cstdio>
#include <string.h>
#pragma warning ( disable : 4996 )
using namespace std; inline int Max(int a,int b) { return a>b?a:b; }
inline int Min(int a,int b) { return a>b?b:a; }
const int inf = 0x3f3f3f3f;
const int maxn = 1e6+; char str[maxn];
int nxt[maxn];
int len, plen, minpos, maxpos; void getNext()
{
memset( nxt, , sizeof(nxt) );
len = strlen(str); int k = -, j = ;
nxt[j] = -; while ( j < len )
{
if ( k==- || str[j]==str[k] )
{
k++; j++;
nxt[j] = k;
}
else
k = nxt[k];
}
plen = nxt[len];
} void getMin()
{
int tmp, i = , j = , k = ;
while ( i<len && j <len && k <len )
{
tmp = str[(i+k)%len]-str[(j+k)%len];
if(!tmp) k++;
else
{
if(tmp>) i += k+;
else j += k+;
if( i == j ) j++;
k = ;
}
}
minpos = i<j?i+:j+;
} void getMax()
{
int tmp, i = , j = , k = ;
while ( i<len && j<len && k<len )
{
tmp = str[(i+k)%len]-str[(j+k)%len];
if(!tmp) k++;
else
{
if(tmp<) i += k+;
else j += k+;
if( i == j ) j++;
k = ;
}
}
maxpos = i<j?i+:j+;
} int main()
{
while ( ~scanf("%s", str) )
{
getNext();
getMin();
getMax(); int tmp = (len%(len-plen)==)?(len/(len-plen)):;
printf( "%d %d %d %d\n", minpos, tmp, maxpos, tmp );
}
return ;
}
最新文章
- NOIP2010关押罪犯[并查集|二分答案+二分图染色 | 种类并查集]
- tomcat启动指定项目
- js中,还真不了解 console
- increadbuild重装
- 6、httpd服务的安装、配置
- Mark一下,一上午就这么过去了,关于客户端连接oracle10G的问题
- html初学(二)
- javascript面向对象学习笔记——创建对象(转)
- Spring MVC url提交参数和获取参数
- 在jsp页面上直接打开PDF文件
- maven使用笔记一 下载json-lib引发的问题
- APIO 2013
- 给div添加2个class
- python修炼第三天
- lr录制脚本中文乱码问题
- 【PAT】B1081 检查密码(15 分)
- CentOS6.5运行yum报错:No module named yum
- 委托、Lambda表达式、事件系列03,从委托到Lamda表达式
- 为什么WEB-INF外的jsp无法根据cookie享受国际化
- 基于jQuery的数字键盘插件