首页 > 试题广场 >

不是烤串故事

[编程题]不是烤串故事

热度指数：1158 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 512M，其他语言1024M
算法知识视频讲解

$\,\,\,\,\,\,\,\,\,$ 小红有两个长度为 $n$ 的字符串 $s$ 和 $t$ ，我们定义下标从 $1$ 开始，现在你可以选取字符串 $s$ 的前 $i$ 个字符 $s_1 s_2\cdots s_i$ ，然后将这一部分反转后与剩余部分拼接，得到 $s_i'$ 。

$\,\,\,\,\,\,\,\,\,$ 请你找到每一个翻转前缀 $s_i'$ 与字符串 $t$ 的 $\displaystyle \max_{i=1}^n{\rm\_len} \{{\rm lcp}(s_i',t) \}$ ，即长度最长的 ${\rm lcp}(s_i',t)$ 。在这里， $\rm lcp$ 代表最长公共前缀。

$\,\,\,\,\,\,\,\,\,$ 好吧，这其实并不难，作为神秘的 $\mathcal F$ 题，你同时需要输出满足上述条件的最小的 $i$ 。

$\,\,\,\,\,\,\,\,\,$ 在本题中，反转即为将字符串绕中心字符前后反转，具体地说，设字符串为 $s_1s_2\cdots s_{n-1} s_n$ ，反转后得到 $s_n s_{n-1}\cdots s_2s_1$ 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入一个整数  代表字符串长度。
第二行输入一个长度为  ，且仅由小写字母构成的字符串 。
第三行输入一个长度为  ，且仅由小写字母构成的字符串 。

除此之外，保证所有的  之和不超过  。

输出描述:

对于每一组测试数据，在一行上输出两个整数，代表最长  长度和在此条件下最小的  。

示例1

输入

3
6
baabaa
aabbbb
3
abc
bac
2
ab
cd

输出

4 3
3 2
0 1

说明

对于第一组测试数据，我们这样描述整个过程：
选择前缀长度为  翻转  ， ；
选择前缀长度为  翻转  ， ；
选择前缀长度为  翻转  ， ；
选择前缀长度为  翻转  ， ；
选择前缀长度为  翻转  ， ；
选择前缀长度为  翻转  ， ；
所以最长的公共前缀为  ，与此同时最小的翻转下标为  。

算法知识视频讲解

WIDA

发表于 2024-08-18 21:02:24

大家好，这里是牛客周赛 Round 56 的组题人。希望大家喜欢这一场的题目~ 从组题人的角度来总体评价这一场，打卡；需要理解一下题意的打卡，注意加粗字体的小骗局；构造+思维+位运算，可能大家对位运算不是很熟悉，但其实思维难度低于；在校招中，位运算是考察较为频繁的知识点，需要大展开全文

kilomatutinal

发表于 2026-03-10 21:06:59

这道题好难喵！给猫猫做傻了喵！借用了蒟蒻果冻01大佬的O(n) 思想，仅仅只是为了让更多人和猫猫一样理解他的思想喵！猫猫解释时间到！(≧▽≦)第一步：看看 t 的开头有几个相同的小可爱设定一个 z 来统计 t 开头有多少个连续相同的字符 int z = 1; while (z + 1 < n 展开全文

蒟蒻果冻01

发表于 2026-03-10 12:30:34

这里直接利用z函数的信息复用思想，可以达到最优的时间复杂度.发现可以先得到从每个开始的和的后缀的LCP的长度，记为数组 b.难点是得到翻转后与的LCP的长度，记为数组 a：设已经得到，此时和的末尾分别加上一个和，如果，那么显然的；否则设与的LCP的长度为，如果，那么与的LCP的长度小于，也展开全文

Laiyiwen_01

发表于 2026-03-10 22:38:07

这有 2200？？？注意到操作是平凡的，我们直接维护整个串的翻转，那么操作就可以简单表示，又因为 lcp 是具有单调性的，考虑二分。于是对于每个，我们可以二分 lcp 的值，然后对于每个二分出来的值，假设当前在处理的答案，二分的答案是，如果，说明这一段全都是需要翻转的，直接处理。如果，展开全文

mipha™

发表于 2024-08-18 21:04:06

思路二分 + 字符串哈希对于每次翻转，二分lcp即可，check函数通过字符串哈希进行哈希值快速获取，然后判断即可。代码 # 字符串哈希 base, mod = 1331, 10**9 + 7 base_inv = pow(base,mod-2,mod) def getPreHash(s): 展开全文