算法高级进阶一
一 、KMP 算法
两个字符串str1,str2;
str1中是否包含str2，如果包含请返回str2开始的位置。
解析：
package com.znst.demo;
import java.util.HashMap;
public class Test {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str1= "aaaaaab";
String str2 ="aaab";
char[] arr1= str1.toCharArray();
char[] arr2 = str2.toCharArray();
int index = getIndexOf(arr1,arr2);
System.out.println("index="+index);
}
private static int getIndexOf(char[] str1, char[] str2) {
// TODO Auto-generated method stub
if(str1==null||str2==null||str1.length==1||str2.length==1||str1.length<str2.length)
return -1;
int i=0;
int j=0;
int[] next =getNextArray(str2);
while(i<str1.length&&j<str2.length) {
if(str1[i]==str2[j]) {
i++;
j++;
}else if(next[j]==-1) {
i++;
}else {
j= next[j];
}
}
return j==str2.length?i-j:-1;
}
private static int[] getNextArray(char[] str) {
// TODO Auto-generated method stub
int[] res = null;
if(str.length==1)return new int[] {-1};
int[] next = new int[str.length];
next[0]=-1;
next[1]=0;
int i=2;
int cn=0;
while(i<next.length) {
if(str[i-1]==str[cn]) {
//next[i++]=++cn;
next[i]=cn+1;
i++;
cn++;
}else if(cn>0) {
cn= next[cn];
}else {
next[i++]=0;
}
}
return next;
}
}
练习一：给你一个原始字符串"abcabc"，只能在后面添加字符，要求组成一个大串，这个大串必须包含两个原始串，且这两个原始串开头位置不一样。
package com.znst.demo;
import java.util.HashMap;
public class Test2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str ="abcabc";
String str1= str+"X";
char[] arr = str1.toCharArray();
int[] next = getNextArray(arr);
String res = str+str.substring(0,next[str.length()]);
System.out.println("res="+res);
}
private static int[] getNextArray(char[] str) {
// TODO Auto-generated method stub
int[] res = null;
if(str.length==1)return new int[] {-1};
int[] next = new int[str.length];
next[0]=-1;
next[1]=0;
int i=2;
int cn=0;
while(i<next.length) {
if(str[i-1]==str[cn]) {
//next[i++]=++cn;
next[i]=cn+1;
i++;
cn++;
}else if(cn>0) {
cn= next[cn];
}else {
next[i++]=0;
}
}
return next;
}
}
练习二：判断一颗树tree1是否包含另一棵树tree2。
示例：
将树***，然后使用kmp算法。
二、Manacher算法
一个字符串中，找到最长回文子串。
-
概念一、回文半径数组
定义一个数组，然后遍历求出每个字符的回文半径，保存在数组里面 -
概念二、最右回文半径右边界
每个元素下，最右回文半径的位置 -
概念三、最右回文右边界对应的中心
记录最早到达右边界的中心。
回文半径数组 [0,1,0,3,0,1,0]
最右回文半径右边界[0,2,2,6,4,6,6]
最右回文右边界对应的中心[0,1,1,4,4,4]
可能性1：
可能性2：i在回文右边界内
可能性3：
可能性4：
时间复杂度分析：
可能性总结：
- i在R外，暴力扩
- i 在R内
- i’的回文，在LR内，O(1)
- i’的回文，在LR外，O(1)
- i’的回文的左边界与L压线，从R的右边界扩
第一种可能性和第四种的可能性 ，总体的代价是使R增加到多大，R从0到n,不回退。因此总体时间复杂度O(n)
package com.znst.demo;
import java.util.HashMap;
public class Test2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str ="zkabatftabaky";
int res = maxLcpsLength(str);
System.out.println("res="+res);
}
private static int maxLcpsLength(String str) {
// TODO Auto-generated method stub
if(str==null||str.length()==0) return 0;
char[] charArr = manacherString(str);
int[] pArr = new int[charArr.length];
int C=-1;
int R=-1;
int max = Integer.MIN_VALUE;
for(int i=0;i!=charArr.length;i++) {
/**
* i'=2*C-i
* pArr[i']=pArr[2*C-i],这是i'的回文半径被包住了，这种情况这段回文半径不需要验证，是回文。
* R-i，这是i'的回文没有被包住，这种情况，R-i是回文，不需要验证。
* 如果i在回文右边界外面，这种情况，只有i自己不需要验证，是回文。
*/
pArr[i]=R>i?Math.min(pArr[2*C-i], R-i):1;
/**
* 这个while包含了4种情况
* 在i+pArr[i]<charArr.length，要验证的区域没有越界，
* i-pArr[i]>-1，左边的区域没有越界，
* 在这两种情况下，都去扩一下，只是第2,3种可能性在扩的时候，会失败。
*/
while(i+pArr[i]<charArr.length&&i-pArr[i]>-1) {
if(charArr[i+pArr[i]]==charArr[i-pArr[i]]) {
pArr[i]++;
}else {
break;
}
}
/**
* 如果超出右边界，则出现新的最大右边界，更新R，C
*/
if(i+pArr[i]>R) {
R = i+pArr[i];
C= i;
}
//记录全局最大值
max= Math.max(max, pArr[i]);
}
return max-1;
}
private static char[] manacherString(String str) {
// TODO Auto-generated method stub
char[] charArr = str.toCharArray();
char[] res = new char[str.length()*2+1];
int index=0;
for(int i =0;i<res.length;i++) {
res[i]=(i&1)==0?'#':charArr[index++];
}
return res;
}
}
案例一：如果只能向字符串后面添加字符，怎么使整体串都变成回文串。要求添加字符最少。
package com.znst.demo;
import java.util.HashMap;
public class Test2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str ="abcd123321";
String res = shortestEnd(str);
System.out.println("res="+res);
}
private static String shortestEnd(String str) {
// TODO Auto-generated method stub
if(str==null||str.length()==0) return null;
char[] charArr = manacherString(str);
int[] pArr = new int[charArr.length];
int index=-1;
int pR=-1;
int maxContainsEnd = -1;
for(int i=0;i!=charArr.length;i++) {
/**
* i'=2*C-i
* pArr[i']=pArr[2*C-i],这是i'的回文半径被包住了，这种情况这段回文半径不需要验证，是回文。
* R-i，这是i'的回文没有被包住，这种情况，R-i是回文，不需要验证。
* 如果i在回文右边界外面，这种情况，只有i自己不需要验证，是回文。
*/
pArr[i]=pR>i?Math.min(pArr[2*index-i], pR-i):1;
/**
* 这个while包含了4种情况
* 在i+pArr[i]<charArr.length，要验证的区域没有越界，
* i-pArr[i]>-1，左边的区域没有越界，
* 在这两种情况下，都去扩一下，只是第2,3种可能性在扩的时候，会失败。
*/
while(i+pArr[i]<charArr.length&&i-pArr[i]>-1) {
if(charArr[i+pArr[i]]==charArr[i-pArr[i]]) {
pArr[i]++;
}else {
break;
}
}
/**
* 如果超出右边界，则出现新的最大右边界，更新R，C
*/
if(i+pArr[i]>pR) {
pR = i+pArr[i];
index= i;
}
//区别：
if(pR==charArr.length) {
maxContainsEnd=pArr[i];
break;
}
}
char[] res = new char[str.length()-maxContainsEnd+1];
for(int i=0;i<res.length;i++) {
res[res.length-1-i]=charArr[i*2+1];
}
return String.valueOf(res);
}
private static char[] manacherString(String str) {
// TODO Auto-generated method stub
char[] charArr = str.toCharArray();
char[] res = new char[str.length()*2+1];
int index=0;
for(int i =0;i<res.length;i++) {
res[i]=(i&1)==0?'#':charArr[index++];
}
return res;
}
}