首页 > 试题广场 >

Just A String

[编程题]Just A String
  • 热度指数：5 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
何老师手中有一个字符串S，他发现这个字符串有一个神奇的性质，取出一个长为i的前缀（就是由S的前i个字符顺序构成的字符串）prei和一个长为j的后缀（就是由S的后j个字符顺序构成的字符串）sufj之后，总是存在三个字符串A,B,C（可能为空）使得prei=A+B,sufj=B+C， 虽然这听起来像是一句废话。 
显然三元组A,B,C不总是唯一的，何老师从所有可能的三元组中找到B最长的，很容易知道这样的三元组是唯一的，并且认为prei和sufj的契合度就是f(i,j)=|A||B|2|C|，现在你需要帮何老师算出所有f(i,j)(0 ≤ i,j ≤ n)的异或和。 
这里|X|表示字符串X的长度，X+Y表示将两个字符串X和Y顺序拼接起来后得到的新字符串。

输入描述:
第一行是一个正整数T(≤ 500)，表示测试数据的组数， 每组测试数据，包含一个仅由小写字母构成的非空字符串S(|S| ≤ 2000)， 保证满足|S|>200的数据不超过5组。


输出描述:
对于每组测试数据，输出所有f(i,j)(0 ≤ i,j ≤ n)的异或和。
示例1

输入

1
abcab

输出

13
算法知识视频讲解
开通博客
头像 苟且的狮子
发表于 2020-08-31 02:24:58
kmp 题意： 分析： 这一题，我最初很没思路。刚开始想会不会是kmp扩展，但是琢磨一番发现无法解决。然后，在进行手工推算时，发现这是个kmp问题。 请看：题目让我们求的是：对于字符串s,判断他的每一个前缀和每一个后缀的B是否？ 从题目所给的数据量来看，我们很简单就能想到枚举。但是，即便枚举我们 展开全文
去ta的博客 赞 (12) 回复(0) 收起

问题信息

kmp与扩展kmp
上传者：牛客301599号
难度：
1条回答 1758浏览

热门推荐

通过挑战的用户

相关试题

Just A String

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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