HDU - 3374 String Problem (kmp求循环节+最大最小表示法)
2024-08-31 23:54:03
做一个高产的菜鸡
传送门: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;
}
最新文章
- 关于 js 一些基本的东西
- ACM ICPC Vietnam National Second Round
- ecshop 签名
- Atom 和 markdown 基本使用
- 7、java实现的两种单例模式
- linux消息队列操作
- swift3.0基础语法
- Oracle 错误码
- 分享QQ第三方登陆SDK
- 创建OpenStack外部网络并分配浮动IP
- 微软Visual Studio二十周年:VS2017于3月7日发布
- Java 多线程(五)—— 线程池基础 之 FutureTask源码解析
- python字符串(string)方法整理
- PHP多维数组转一维
- MVC4 下DropDownList使用方法(转)
- CocosCreator弹窗处理
- PHP 7下安装Swoole和Yar、Yaf
- 使用pycharm,追求最优的代码。
- 【BZOJ3309】DZY Loves Math 解题报告
- Less &; Sass