做一个高产的菜鸡

传送门:HDU - 3374

题意:多组输入,给你一个字符串,求它最小和最大表示法出现的位置和次数。

题解:刚刚学会最大最小表示法,amazing.. 次数就是最小循环节循环的次数。

#include<bits/stdc++.h>
using namespace std; int nt[1000100],b[1000100];
char a[1000100]; void kmp_nt(int m)
{
int i,j;
i = 0;
nt[0] = j =-1;
while(i < m){
while(j!=-1&&a[i]!=a[j])
j = nt[j];
if(a[i]==a[j]||j==-1){
i++;
j++;
nt[i]=j;
}
}
} int Getmin(char s[])
{
int n = strlen(s);
int i = 0,j = 1,k = 0,t;
//表示从i开始k长度和从j开始k长度的字符串相同
while(i<n&&j<n&&k<n){
t = s[(i+k)%n]-s[(j+k)%n];
//t用来计算相对应位置上那个字典序较大
if(!t) k++;//字符相等的情况
else{
if(t>0) i+=k+1;//i位置大,最大表示法: j += k+1
else j+=k+1;//j位置大,最大表示法: i += k+1
if(i==j) j++;
k=0;
}
}
return i>j?j:i;
} int GetMax(char s[]){
int len = strlen(s);
int i=0,j=1,k=0;
while(i<len&&j<len&&k<len){
int t=s[(i+k)%len]-s[(j+k)%len];
if(t==0)k++;
else{
if(t>0)j=j+k+1;
else i=i+k+1;
if(i==j)j++;
k=0;
}
}
return i<j?i:j;
} int main()
{
while(scanf("%s",a)!=EOF){
int len=strlen(a);
kmp_nt(len);
int k=1;
int ans=len-nt[len];
if(len%ans==0) k=len/ans;
int mi=Getmin(a);
int ma=GetMax(a);
cout<<mi+1<<' '<<k<<' '<<ma+1<<' '<<k<<endl;
}
return 0;
}

最新文章

  1. 关于 js 一些基本的东西
  2. ACM ICPC Vietnam National Second Round
  3. ecshop 签名
  4. Atom 和 markdown 基本使用
  5. 7、java实现的两种单例模式
  6. linux消息队列操作
  7. swift3.0基础语法
  8. Oracle 错误码
  9. 分享QQ第三方登陆SDK
  10. 创建OpenStack外部网络并分配浮动IP
  11. 微软Visual Studio二十周年:VS2017于3月7日发布
  12. Java 多线程(五)—— 线程池基础 之 FutureTask源码解析
  13. python字符串(string)方法整理
  14. PHP多维数组转一维
  15. MVC4 下DropDownList使用方法(转)
  16. CocosCreator弹窗处理
  17. PHP 7下安装Swoole和Yar、Yaf
  18. 使用pycharm,追求最优的代码。
  19. 【BZOJ3309】DZY Loves Math 解题报告
  20. Less &amp; Sass

热门文章

  1. SqlLoad的简单使用
  2. Flutter 基础组件:Widget简介
  3. Tomcat-8.5.23 基于域名和端口的虚拟主机
  4. 【Linux】fio测试读写速度
  5. 【RAC】安装cluster软件 在节点2执行root.sh脚本
  6. HarmonyOS三方件开发指南(5)——Photoview组件
  7. kubernets之pod的标签的使用
  8. 针对Linux系统主机,进入修复模式,解决开机报错问题
  9. 以我的亲身经历,聊聊学python的流程,同时推荐学python的书
  10. JavaScript中创建对象的三种方式!