jialiang.bao
BAN USERUsing DP, my code is based on Java. The time complexity is O(n^2)
public static int[] getLongest(String str){
char[] data = str.toCharArray();
int[] index = new int[data.length];
int[] buffer = new int[256]; //store pre index
int max = 0;
int[] span = new int[2];
for(int i = data.length - 1; i >= 0; i--){
index[i] = buffer[data[i]] == 0 ? -1 : buffer[data[i]];
buffer[data[i]] = i;
}
for(int i = 0; i < index.length && index[i] != -1 ; i++){
int cur = i;
int j = index[i];
while(j != -1){
for(; j != -1; j = index[j]){
if(isPaloindromes(data,cur,j) == true){
if(max < j - cur + 1){
max = j - cur + 1;
span[0] = cur;
span[1] = j;
}
}
}
int tmp = cur;
index[tmp] = -1;
cur = index[cur];
j = cur == -1 ? -1 : index[cur];
}
}
return span;
}
public static boolean isPaloindromes(char[] data, int i, int j){
int mid = (i + j) / 2;
for(int k = 0; k < mid; k++){
if(data[i + k] != data[j - k])
return false;
}
return true;
}
public static int[] getLongest(String str){
char[] data = str.toCharArray();
int[] index = new int[data.length];
int[] buffer = new int[256]; //store pre index
int max = 0;
int[] span = new int[2];
for(int i = data.length - 1; i >= 0; i--){
index[i] = buffer[data[i]] == 0 ? -1 : buffer[data[i]];
buffer[data[i]] = i;
}
for(int i = 0; i < index.length && index[i] != -1 ; i++){
int cur = i;
int j = index[i];
while(j != -1){
for(; j != -1; j = index[j]){
if(isPaloindromes(data,cur,j) == true){
if(max < j - cur + 1){
max = j - cur + 1;
span[0] = cur;
span[1] = j;
}
}
}
int tmp = cur;
index[tmp] = -1;
cur = index[cur];
j = cur == -1 ? -1 : index[cur];
}
}
return span;
}
public static boolean isPaloindromes(char[] data, int i, int j){
int mid = (i + j) / 2;
for(int k = 0; k < mid; k++){
if(data[i + k] != data[j - k])
return false;
}
return true;
}
Using DP to solve this problem. maybe o(n^2)
- jialiang.bao August 12, 2013