【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)。
Read full article from 【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)的复杂度，找出所有的前缀，然后对每一个前缀求其最长重复词，如何定义这个最长重复词的规则呢？同时也可以看出每一个前缀和其前一个前缀的最长重复词之前是有一定的规律的，首先是求其真前缀，然后根据前缀，进行拼接，拼接后验证该字符串是否包含其中。因为要找最大的重复词，而且其还要将当前的字符串包含在其中，所以该前缀一定要大于等于当前前缀长度的一半，因此我们在找子串的时候，从其长度一半开始。然后从字符串的第一个开始和字符串的中间位置进行判断比对。因此写出如下代码。
public static long getLongest(int n, String s) {
// write code here
long length = 0;
if(n==0||s==null||s.length()==1)
return length;
for(int i=1; i<s.length(); i++){
long tmpLength1=0;
for(int j=i/2; j<i; j++){
long tmpLength2 = 0;
for(int k=0; k<=j&&(s.charAt(k)==s.charAt(j+k+1)); k++){
if((j+k+1)==i){
tmpLength2 = j+1;
break;
}
}
if(tmpLength2>tmpLength1)
tmpLength1 = tmpLength2;
}
length+=tmpLength1;
}
return length;
}
显然这复杂度是不能够忍受的，然后考虑再进行优化。当然此处的第三重循环可以通过借助java中提供的类库方法来减少一重循环。但是复杂度的问题还是没有解决，只是代码上看起来是复杂度减轻了。实际上是并没有太大的变化，同时上面的代码中写的两个局部变量进行的值的控制感觉这种写法很是拙劣。
问题进一步探索
先前的思路是从中间开始作为其最小的重复词，然后进行开始位置和设置的中间位置之后的节点的比对，比对到最后一个节点如果比对成功则证明可以，找到最长的一个，但是复杂度攀升至n3，再进一步寻找规律，从每一个重复词向上攀升寻找，这样找到一个重复词，然后向后判断其可能成为那些子串的重复词。判断规则是，找到该子串，从零开始扫一下，扫到结尾，即可确认其是否符合。复杂度为n^2
代码实现2
public static long getLongest2(int n,String s){
long length=0;
if(n==0||s==null||s.length()==1)
return length;
if(s.charAt(1)==s.charAt(0))
length++;
int [] subLength = new int [n];
for(int i=0; i<n; i++)
subLength[i] = 0;
for(int i=1; i<n; i++){
for(int j=1; j<=(i+1)&&(i+j)<n; j++){
if(s.charAt(i+j)==s.charAt(j-1))
subLength[i+j] = i+1;
else break;
}
}
for(int tmp:subLength){
System.out.println(tmp);
length+=tmp;
}
return length;
}
这里的最开始的判断是用来判断前两位字符是否相同，对于代码优化一下，可以将其与下面的循环进行合并。
优化与思考
现在感觉相比于最初刷题状态有了很大提升，开始的时候无法深入的去思考，总是着急动手，出了错误就是去搜答案，然后对着答案自己写，最后效果非常不好，一反面反映出了畏难心理，另一方面表现出了浮躁，着急，追求题量而不去强调质量，最终一无所获。比如记笔记，看书的时候去勾画，想着以后再去复习，现在感觉也看的差不多得了，其实以后基本上是不会去看了，感动自己，最终还是什么都不会，踏踏实实的一个题目一个题目的慢慢来。
解题方法上，要做的事抽象出了问题的模型，然后从中寻找规律，根据规律进行编程。先不考虑最优，想出来一个方法之后，再进行不断的优化。今天就是这样了。
解题方法上，要做的事抽象出了问题的模型，然后从中寻找规律，根据规律进行编程。先不考虑最优，想出来一个方法之后，再进行不断的优化。今天就是这样了。
