hdu-1358 KMP

el/2024/2/25 23:15:12

思路

题目意思简单来说就是给定字符串,求该字符串的最小周期长度。

关于周期

符号约定:t表示一个周期,kt表示k个周期构成的字符串,即tttttt…t,共k个t,k代表周期数,‘+’表示连接字符串

  • 每个前缀至少可以看成一个周期
  • 我们首先找到的必然是形如2t的周期数大于1的前缀
  • 若字符串s=kt+t,则s的周期也为t,周期为(k+1)(看起来是废话)
  • 结合 (2)(3),可以归纳出我们通过kt+t的方式找到的周期字符串的周期长度是最小的。
    结合kmp来看:
  • 若s为周期字符串,周期数k>1,则s=(k-1)t+t=t+(k-1)t。因此有结论,若字符串存在长为(k-1)t的最长前后缀匹配,且剩余部分恰好是一个周期长度,则,字符串是一个周期为k的周期字符串,简单证明如下:
    在这里插入图片描述
    显然,红色部分匹配可知,t1=t2=t3,即该字符串也是周期为t的字符串。

解法

有了如上结论就好求解了。

  • 先使用kmp预处理字符串,求出所有最长前后缀匹配。
  • 根据上一步结果若某前缀的最长前后缀匹配满足上述结论的条件的话,则可求出该前缀的最小周期。
  • 最后根据题目要求输出就可以了

代码实现(c++)

#include<stdio.h>
#include<string.h>
int nxt[1000005];
char str[1000005];
int tt[1000005];
int n;
void kmp_pre(char *s,int l)
{nxt[0]=-1;int i=-1,j=0;while(j<l){while(i!=-1&&s[i]!=s[j]) i =nxt[i];nxt[++j]=++i;}
}
int main()
{int t=0;while(~scanf("%d",&n)&&n){getchar();gets(str);kmp_pre(str,n);for(int i=0;i<n;i++){tt[i]=i+1;if(nxt[i+1]!=0&&nxt[i+1]%tt[nxt[i+1]-1]==0&&i+1-nxt[i+1]==tt[nxt[i+1]-1]) tt[i]=tt[nxt[i+1]-1];//这里对应判断条件}printf("Test case #%d\n",++t);for(int i=0;i<n;i++){if((i+1)/tt[i]>1)printf("%d %d\n",i+1,(i+1)/tt[i]);}puts("");}return 0;
}

http://www.ngui.cc/el/4894914.html

相关文章

leetcode 87 Scramble String(c++,beat 80%~100%)

题解 符号&#xff1a; S_(i-j):表示字符串s下标从i到j的字串。 思路 其实没什么规律&#xff0c;就是暴力枚举交换轴&#xff0c;然后每次有交换与不交换两种情况&#xff0c;递归判断是否可行。唯一剪枝就是假如S1_(i,j)S2_(k,l)&#xff0c;则他们所包含的字母的集合是相…

【leetcode 142】 Linked List Cycle II 链表找环

链表找环 https://leetcode.com/problems/linked-list-cycle-ii/ class Solution(object):def detectCycle(self, head):""":type head: ListNode:rtype: bool"""p1 headp2 headwhile p1 is not None and p1.next is not None:p1p1.next.nex…

VirtualBox安装增强工具时:Unable to install guest additions: unknown filesystem type 'iso9660'

搬运一下答案&#xff08;原文地址https://askubuntu.com/questions/596998/unable-to-install-guest-additions-unknown-filesystem-type-iso9660?newreg2d19e8256398418aa9fefb792def28a8&#xff09;&#xff0c;原因如答主所说。

【pyqt5】拖拽绘制矩形框

博主想自己做一个图片标注工具&#xff0c;用于制作目标检测数据集&#xff0c;其中一个功能就是拖拽鼠标选中矩形区域&#xff0c;参考了几篇博客&#xff0c;自己实现了一下&#xff0c;效果如下&#xff1a; 下面是实现&#xff1a; import sys,math from PyQt5.QtGui imp…

【numpy】ndarray交换两行(两列)、重新排列

numpy进行行(列)交换非常简便&#xff0c;因为numpy的下标访问是基于视图机制的&#xff0c;对子视图重新赋值即可。 a np.arange(12).reshape(3, 4) print(a) a[[0, 2]] a[[2, 0]] a运行结果: [[ 0 1 2 3][ 4 5 6 7][ 8 9 10 11]] array([[ 8, 9, 10, 11],[ 4, 5…

【python】python的for-else语法解释

若for循环正常结束&#xff0c;则执行else&#xff0c; 若for循环break&#xff0c;则不执行else。 for item in container:if search_something(item):# Found it!process(item)break else:# Didnt find anything..not_found_in_container()

【python】编码互转(16进制|bytes|base64|字符串)

基于python3 # 16进制转bytes byte_arr bytes.fromhex("1f2f3f4f") # bytes转16进制 byte_arr.hex() # bytes转base64&#xff0c;输入输出都是bytes import base64 base64.b64encode(byte_arr) # base64转bytes base64.b64decode(base64_byte_arr) # 字符串转byte…

【spark】spark dataframe空值·部分原因

数据类型不一致导致的空值 今天在写一个spark job(pyspark)时又遇到了&#xff0c;又遇到了数据处理的两大拦路虎之一的空数据问题&#xff0c;检查数据源&#xff0c;确定不会有空值后&#xff0c;开始检查代码。最终发现是代码之前的维护者使用了一个字符串作为一个long typ…

【git】强制使用远程分支(git pull -f ?)

git reset --hard origin/your-branch参考 https://stackoverflow.com/questions/1125968/how-do-i-force-git-pull-to-overwrite-local-files