首页 > 试题广场 >

MagicString

[编程题]MagicString
  • 热度指数：532 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
牛妹有有两个字符串与，她想知道在中的哪一个循环同构串中的出现次数最多，如果有多个，请输出字典序最小的一个。

循环同构串的定义：不断地将的部分提前到之前，得到一个新的字符串，这些新的字符串称为循环同构串。
例：的循环同构串为：,,,。


如果没有在的任意一个循环同构串中出现则返回
否则返回字符串代表答案。

示例1

输入

"aaabaaa","aaaa"

输出

"aaaaaab"

说明

包含 次并且字典序最小

备注:
包括，只由小写字母构成
算法知识视频讲解
开通博客
头像 Tag_Kausal
发表于 2020-02-07 10:53:16
解法1：AC首先来看循环同构串如何进行处理？发现其实只需要拓展一倍的长度就可以表示所有的循环同构串了。紧接着是如何确定最多的出现次数。这个我们一般会考虑进行处理，只需要统计一下每个位置是否匹配成功，然后用前缀和进行记录，之后直接做差就能得到在每一个循环同构串中的出现次数了。最后就是如何找到字典序最小 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Maokt
发表于 2021-08-07 18:49:09
算法思想一：枚举 解题思路： 遍历S1的每一个位置使用substr函数进行同构操作，每一个同构串在其中找到S2出现的次数，如果次数更多直接更新，如果次数相等则比较字典序后更新。 图解： 代码展示： C++版本 class Solution { public: 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 xqxls
发表于 2021-08-10 12:36:28
题意整理 给定两个字符串S1和S2。 求S2在S1的哪一个循环同构串中出现次数最多。 如果有多个这样的同构串，输出字典序最小的那一个。 方法一（kmp） 1.解题思路 首先初始化计数数组。 通过kmp算法，获取S2在同构串中出现的次数。 记录最大的出现次数。 通过最大出现次数定位到同构串起点索 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-08-04 14:21:19
思路： 题目的主要信息： 循环同构串：遍历字符串，每到一个字符的时候，将其及后面的字符接到最前面，公式为 要在S1的所有循环同构串中找到出现S2次数最多的一个，若相同次数则返回字典序最小 两个字符串只由小写字母构成 方法一：暴力法具体做法：遍历S1的每一个位置使用substr函数进行同构操作，每 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 认认真真coding
发表于 2021-08-03 14:02:11
题目描述牛妹有有两个字符串S1与S2，她想知道S2在S1中的哪一个循环同构串中的出现次数最多，如果有多个，请输出字典序最小的一个。循环同构串的定义：不断地将si...sn的部分提前到s1...si−1之前,得到一个新的字符串，这些新的字符串称为循环同构串。例：abcc的循环同构串为：abcc,bcc 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

二分 字符串 后缀数组 哈希
难度：
1条回答 7498浏览

热门推荐

通过挑战的用户

查看代码

相关试题

MagicString

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号