求字符串最小表示的方法
(1) 利用两个指针p1, p2。初始化时p1指向s[0], p2指向s[1]。
(2) k = 0开始,检验s[p1+k] 与 s[p2+k] 对应的字符是否相等,如果相等则k++,一直下去,直到找到第一个不同,(若k试了一个字符串的长度也没找到不同,则那个位置就是最小表示位置,算法终止并返回)。则该过程中,s[p1+k] 与 s[p2+k]的大小关系,有三种情况:
(A). s[p1+k] > s[p2+k],则p1滑动到p1+k+1处 --- 即s1[p1->p1+k]不会
是该循环字符串的“最小表示”的前缀。 k置为0
(B). s[p1+k] < s[p2+k],则p2滑动到p2+k+1处,k置为0
(C). s[p1+k] = s[p2+k],则 k++; if (k == len) 返回结果。
注:这里滑动方式有个小细节,若滑动后p1 == p2,将正在变化的那个指针再+1。直到p1、p2把整个字符串都检验完毕,返回两者中小于 len 的值。
(3) 如果 k == len, 则返回p1与p2中的最小值
如果 p1 >= len 则返回p2
如果 p2 >= len 则返回p1
(4) 进一步的优化,例如:p1要移到p1+k+1时,如果p1+k+1 <= p2的话,可以直接把p1移到 p2之前,因为,p2到p2+k已经检验过了该前缀比以p1到p1+k之间任何一个位前缀都小;p2时的类似,移动到p1+1。
--------------------------------------------------------------------------------------------------------------------------以上内容为转帖------------------------------------------------
然后我求出现次数的方法是构造一个字符串,是原始字符串复制一次衔接后的结果,然后去掉最后一位, 用KMP算法在这个字符串中寻找最小表示和最大表示的字符串的个数即可。最大表示有个巧妙的方法,新取一个字符串,将值都改为原字符串的负值,求出来即为最大表示。实际上不用这么麻烦,直接从next数组中就能得到答案,但是我还没理解,就先用这个比较笨的方法了、
分享到:
相关推荐
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
2、new做两件事,一是分配内存,二是调用类的构造函数 3、new建立的是一个对象,而malloc分配的是一块内存 4、new/delete是保留字,不需要头文
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs
上面可能有poj的题目,hdu的题目,spoj的题目,sgu的题目,hust上的题目,fzu上的题目
ACM题库,一些题目和答案,以及解题报告,传上来共享
杭电OnlineJudge 200-2099的解题报告
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。...
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
hdu 1695 GCD(欧拉函数+容斥原理).docx
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
acm hdu as easy as a+b
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
acm入门训练和日常训练 对于初学者以及acm爱好者有叫大帮助
杭电ACMhdu1163
HDU1059的代码
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
hdu1001解题报告
hdu 1574 passed sorce