BZOJ 2176 Strange string ——最小表示法
2024-08-30 03:26:44
本来想用来练习后缀自动机的,但是100w有点虚(事实证明确实T掉了)。
只好上最小表示法。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define uch unsigned char uch s[10000005];
int l,pos; int main()
{
scanf("%d",&l);
scanf("%s",s+1);
int i,j,k;
i=1;j=2;k=0;
while (i<=l&&j<=l)
{
k=0;
while (s[(i+k-1)%l+1]==s[(j+k-1)%l+1]&&k<=l) k++;
if (k==l) return i;
if (s[(i+k-1)%l+1]>s[(j+k-1)%l+1])
{
if (i+k+1>j) i=i+k+1;
else i=j+1;
}
else
{
if (j+k+1>i) j=j+k+1;
else j=i+1;
}
pos=min(i,j);
}
F(i,1,l) printf("%c",s[(i+pos-1-1)%l+1]);
}
最新文章
- CentOS 7 修改主机名
- 算法训练 Torry的困惑(基本型)
- USB设备的基本概念
- Golang学习 - sort 包
- 【转】深入研究java.lang.Runtime类
- Eclipse搭建服务器
- Spring AOP + AspectJ Annotation Example---reference
- Facebook登录 AndroidStudio
- [LeetCode]题解(python):134-Gas Station
- 设计模式总结1--observer pattern
- HttpServletResponse应用----生成验证码
- cstring头文件函数解析
- 用php+mysql+ajax实现淘宝客服或阿里旺旺聊天功能 之 前台页面
- 团队作业4——第一次项目冲刺(Alpha版本)2017.4.25
- web服务器负载均衡与集群基本概念二
- day08-(xml&;&;tomcat)
- 转:10分钟了解JS堆、栈以及事件循环的概念
- Oracle(转换函数)
- ReactiveX 学习笔记(11)对 LINQ 的扩展
- python使用cv2显示图片像素值
热门文章
- iOS之创建CocoaPods公有库教程
- leetcode 127 单词接龙
- Codeforces Round #318 (Div. 2) A 	 Bear and Elections (优先队列模拟,水题)
- (五)VMware Harbor 部署之SSL
- 手把手教你打造一个 Mac 风格的 Windows10(手动滑稽)
- Ubuntu12.04安装Chrome浏览器,并添加到左侧的启动栏
- httpClient类
- java在线聊天项目0.3版本 制作客户端窗体,实现发送按钮和回车发送信息功能,使用ActionListener监听事件中actionPerformed方法(用内部类和匿名内部类两种方法)
- 【最长连续零 线段树】bzoj1593: [Usaco2008 Feb]Hotel 旅馆
- CSS3-盒模型-resize属性