【Everyday】(2)重复词 - Everyday - SegmentFault
对于两个字符串B和C，我们定义BC为将C接在B的后面形成的新串。一个字符串P是串A的前缀，当且仅当存在B使得A＝PB，当然B可以为空串。若P!=A,则我们称P为A的真前缀。现在定义重复词。串Q是串A的重复词当且仅当Q是A的真前缀，且A是QQ的前缀。而A的最长重复词则是A的重复词中最长的一个，或者空串（当A没有任何重复串时）。如ababab的最长重复词是abab;abc的最长重复词是空串。
给定一个串s(由字母组成)，及它的长度n(1≤n≤100000)，请返回s的所有前缀的最长重复词的长度之和(空串长度为0)。
测试样例：
8,"babababa"
返回：24
解题思路
题目中给出了很多的新概念，先是对这些概念进行一个理解，但是直接从概念去看，去理解，还是有些困难的，而且容易走偏，导致后面写代码通不过，而且找不出原因来，可以先根据测试样例和自己对概念的理解来进一步加深问题的定义，实现是s的前缀有哪些？根据概念我们可以得到{null,b,ba,bab,baba,babab,bababa,bababab,babababa},然后是求最长重复词，这个根据概念可知，最长重复词是Q是A的真前缀，而且A是QQ的前缀，据此我们可以得到:null,b,ba是不具有重复词的，而bab的重复词是ba，baba的重复词是ba，babab的重复词是baba,bababa的重复词是baba,bababab的重复词是bababa,babababa的最长重复词是bababa.共24个。大致解题思路为先求前缀，然后再找最长重复词，O(n)的复杂度，找出所有的前缀，然后对每一个前缀求其最长重复词，如何定义这个最长重复词的规则呢？同时也可以看出每一个前缀和其前一个前缀的最长重复词之前是有一定的规律的，首先是求其真前缀，然后根据前缀，进行拼接，拼接后验证该字符串是否包含其中。因为要找最大的重复词，而且其还要将当前的字符串包含在其中，所以该前缀一定要大于等于当前前缀长度的一半，因此我们在找子串的时候，从其长度一半开始。然后从字符串的第一个开始和字符串的中间位置进行判断比对。因此写出如下代码。
Read full article from 【Everyday】(2)重复词 - Everyday - SegmentFault
No comments:
Post a Comment