09-01 09:19 武汉大学 Java 发布于美国
关注
求各位大佬看看这道题有没有非暴力解法
最近在刷面经，有一道把我难住了，只想到暴力解检测超时，想问问各位大佬有没有非暴力解法
我们定义两个字符串 S 和 T 的后缀匹配（suffix match）为两个字符串共有的最长后缀的长度。
例如：suffixmatch("xyz", "wyz") == 2，因为这两个字符串共有的后缀是“yz”；而 suffixmatch("aaa", "aaab") == 0，因为这两个字符串的最后一个字符不同，因此共有的后缀是空字符串。
请完成函数 suffixSum，该函数计算字符串 S 与它的每一个前缀（包括字符串本身作为最长前缀）的后缀匹配之和。
比如输入是 ababaa
输出是 9
字符串的前缀是：ababaa、ababa、abab、aba、ab 和 a。每个前缀与字符串 ababaa 的后缀匹配分别是 6、1、0、1、0、1。因此输出结果是 6 + 1 + 0 + 1 + 0 + 1 = 9。
我们定义两个字符串 S 和 T 的后缀匹配（suffix match）为两个字符串共有的最长后缀的长度。
例如：suffixmatch("xyz", "wyz") == 2，因为这两个字符串共有的后缀是“yz”；而 suffixmatch("aaa", "aaab") == 0，因为这两个字符串的最后一个字符不同，因此共有的后缀是空字符串。
请完成函数 suffixSum，该函数计算字符串 S 与它的每一个前缀（包括字符串本身作为最长前缀）的后缀匹配之和。
比如输入是 ababaa
输出是 9
字符串的前缀是：ababaa、ababa、abab、aba、ab 和 a。每个前缀与字符串 ababaa 的后缀匹配分别是 6、1、0、1、0、1。因此输出结果是 6 + 1 + 0 + 1 + 0 + 1 = 9。
全部评论
给个off吧要我做什么都行
华中科技大学 Java
看起来是后缀数组
人才池是我家
美团_后端开发(准入职员工)
后缀数组的思想吧，ababaa按照反向的后缀排序(前缀从右往左比字典序)，比如ababaa的前缀排序下来是a,ababaa,aba,ababa,ab,abab，接着从右往左枚举ababaa，二分查找最后一位为a的数量，再最后一位得到的lr基础上继续二分倒数第二位为a的数量，。。。求和
天翼云科技有限公司
校招火热招聘中
官网直投
相关推荐
投递美团等公司10个岗位 >
查看4道真题和解析 
深圳市睿联技术股份有限公司
| 校招
| 29个岗位
深圳市睿联技术股份有限公司公司福利 15人发布 点赞 评论 收藏
分享
08-17 12:18
华南农业大学 前端工程师 点赞 评论 收藏
分享