HDIU 3374 String Problem(字符串最小最大表示法模板+kmp)

2023-11-10 00:38

本文主要是介绍HDIU 3374 String Problem(字符串最小最大表示法模板+kmp),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

String Problem

Problem Description
Give you a string with length N, you can generate N strings by left shifts. For example let consider the string “SKYLONG”, we can generate seven strings:
String Rank 
SKYLONG 1
KYLONGS 2
YLONGSK 3
LONGSKY 4
ONGSKYL 5
NGSKYLO 6
GSKYLON 7
and lexicographically first of them is GSKYLON, lexicographically last is YLONGSK, both of them appear only once.
  Your task is easy, calculate the lexicographically fisrt string’s Rank (if there are multiple answers, choose the smallest one), its times, lexicographically last string’s Rank (if there are multiple answers, choose the smallest one), and its times also.
 
Input
  Each line contains one line the string S with length N (N <= 1000000) formed by lower case letters. 

Output
Output four integers separated by one space, lexicographically fisrt string’s Rank (if there are multiple answers, choose the smallest one), the string’s times in the N generated strings, lexicographically last string’s Rank (if there are multiple answers, choose the smallest one), and its times also.
 
Sample Input
abcder aaaaaa ababab
 
Sample Output
1 1 6 1 1 6 1 6 1 3 2 3


题意:

循环移位,一直移到尾变成头,对于中间的出现的情况,在里面找字典序最小的和字典序最大的下标标号,然后把其对应次数也输出来。

分析:

循环移位的次数显然是最小循环节的最大周期数,套一个最大和最小表示法就ok了。

#include<cstdio>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<functional>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<map>
using namespace std;const int N = 1000002;
int nxt[N];
int k;
void getnxt(char T[],int tlen)
{int j, k;j = 0; k = -1;nxt[0] = -1;while(j < tlen){if(k == -1 || T[j] == T[k]){nxt[++j] = ++k;if (T[j] != T[k]) nxt[j] = k; } elsek = nxt[k];}
}
//最小表示法
int get_minstring(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)i+=k+1;elsej+=k+1;if(i==j) j++;k=0;}}return min(i,j);
}//最大表示法
int get_maxstring(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+=k+1;elsei+=k+1;if(i==j) j++;k=0;}}return min(i,j);
}
char str[N];
int main()
{while(scanf("%s",str)!=EOF){int len = strlen(str);getnxt(str,len);int tt = len - nxt[len];int num = 1;if(len%tt == 0){num = len/tt;}int posmin = get_minstring(str);int posmax = get_maxstring(str);printf("%d %d %d %d\n",posmin+1,num,posmax+1,num);}return 0;
}

 

这篇关于HDIU 3374 String Problem(字符串最小最大表示法模板+kmp)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/379391

相关文章

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

MySQL 获取字符串长度及注意事项

《MySQL获取字符串长度及注意事项》本文通过实例代码给大家介绍MySQL获取字符串长度及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 获取字符串长度详解 核心长度函数对比⚠️ 六大关键注意事项1. 字符编码决定字节长度2

Springboot3+将ID转为JSON字符串的详细配置方案

《Springboot3+将ID转为JSON字符串的详细配置方案》:本文主要介绍纯后端实现Long/BigIntegerID转为JSON字符串的详细配置方案,s基于SpringBoot3+和Spr... 目录1. 添加依赖2. 全局 Jackson 配置3. 精准控制(可选)4. OpenAPI (Spri

使用Python实现base64字符串与图片互转的详细步骤

《使用Python实现base64字符串与图片互转的详细步骤》要将一个Base64编码的字符串转换为图片文件并保存下来,可以使用Python的base64模块来实现,这一过程包括解码Base64字符串... 目录1. 图片编码为 Base64 字符串2. Base64 字符串解码为图片文件3. 示例使用注意

java String.join()方法实例详解

《javaString.join()方法实例详解》String.join()是Java提供的一个实用方法,用于将多个字符串按照指定的分隔符连接成一个字符串,这一方法是Java8中引入的,极大地简化了... 目录bVARxMJava String.join() 方法详解1. 方法定义2. 基本用法2.1 拼接

golang float和科学计数法转字符串的实现方式

《golangfloat和科学计数法转字符串的实现方式》:本文主要介绍golangfloat和科学计数法转字符串的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望... 目录golang float和科学计数法转字符串需要对float转字符串做处理总结golang float

Python如何判断字符串中是否包含特殊字符并替换

《Python如何判断字符串中是否包含特殊字符并替换》这篇文章主要为大家详细介绍了如何使用Python实现判断字符串中是否包含特殊字符并使用空字符串替换掉,文中的示例代码讲解详细,感兴趣的小伙伴可以了... 目录python判断字符串中是否包含特殊字符方法一:使用正则表达式方法二:手动检查特定字符Pytho

MySQL 字符串截取函数及用法详解

《MySQL字符串截取函数及用法详解》在MySQL中,字符串截取是常见的操作,主要用于从字符串中提取特定部分,MySQL提供了多种函数来实现这一功能,包括LEFT()、RIGHT()、SUBST... 目录mysql 字符串截取函数详解RIGHT(str, length):从右侧截取指定长度的字符SUBST

Python将字符串转换为小写字母的几种常用方法

《Python将字符串转换为小写字母的几种常用方法》:本文主要介绍Python中将字符串大写字母转小写的四种方法:lower()方法简洁高效,手动ASCII转换灵活可控,str.translate... 目录一、使用内置方法 lower()(最简单)二、手动遍历 + ASCII 码转换三、使用 str.tr