一开始没太看懂什么意思,拿笔反复推了一遍才大概知道最大最小表示法是怎么求的,感觉太神奇了...

 #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 ;
}

最新文章

  1. NOIP2010关押罪犯[并查集|二分答案+二分图染色 | 种类并查集]
  2. tomcat启动指定项目
  3. js中,还真不了解 console
  4. increadbuild重装
  5. 6、httpd服务的安装、配置
  6. Mark一下,一上午就这么过去了,关于客户端连接oracle10G的问题
  7. html初学(二)
  8. javascript面向对象学习笔记——创建对象(转)
  9. Spring MVC url提交参数和获取参数
  10. 在jsp页面上直接打开PDF文件
  11. maven使用笔记一 下载json-lib引发的问题
  12. APIO 2013
  13. 给div添加2个class
  14. python修炼第三天
  15. lr录制脚本中文乱码问题
  16. 【PAT】B1081 检查密码(15 分)
  17. CentOS6.5运行yum报错:No module named yum
  18. 委托、Lambda表达式、事件系列03,从委托到Lamda表达式
  19. 为什么WEB-INF外的jsp无法根据cookie享受国际化
  20. 基于jQuery的数字键盘插件

热门文章

  1. Java中循环体的初步了解以及另一种随机数的获取方法
  2. springcloud ribbon Finchley 版本,自定义算法
  3. godaddy账号以及域名被盗找回经历以及网络信息安全的思考
  4. Python全栈开发:线程代码实例
  5. 初探Remax微信小程序
  6. Swimming Balls
  7. 解决Mybatis的invalid bound statement (not found)异常
  8. 阿里重磅开源首款自研科学计算引擎Mars,揭秘超大规模科学计算
  9. 2-sat——输出方案poj3683
  10. MySQL 中LIMIT的使用详解