我需要编写一个方法,其中给我一个字符串s
,并且我需要两次返回包含s
的最短字符串作为一个连续的子字符串。
但是,两次出现的s
可能会重叠。例如,
aba
返回ababa
xxxxx
返回xxxxxx
abracadabra
返回abracadabracadabra
到目前为止,我的代码是:
import java.util.Scanner;
public class TwiceString {
public static String getShortest(String s) {
int index = -1, i, j = s.length() - 1;
char[] arr = s.toCharArray();
String res = s;
for (i = 0; i < j; i++, j--) {
if (arr[i] == arr[j]) {
index = i;
} else {
break;
}
}
if (index != -1) {
for (i = index + 1; i <= j; i++) {
String tmp = new String(arr, i, i);
res = res + tmp;
}
} else {
res = res + res;
}
return res;
}
public static void main(String args[]) {
Scanner inp = new Scanner(System.in);
System.out.println("Enter the string: ");
String word = inp.next();
System.out.println("The requires shortest string is " + getShortest(word));
}
}
我知道我可能在算法层面上错了,而不是在编码层面上。我的算法应该是什么?
发布于 2012-07-15 16:42:09
使用suffix tree。特别是,在为s
构建了树之后,转到表示整个字符串的叶子并向上移动,直到看到另一个字符串结束标记。这将是最长后缀的叶,也是s
的前缀。
发布于 2012-07-15 20:07:13
正如@phs已经说过的,部分问题可以转化为“找到s的最长前缀,也是s的后缀”,没有树的解决方案可能是这样的:
public static String getShortest(String s) {
int i = s.length();
while(i > 0 && !s.endsWith(s.substring(0, --i)))
;
return s + s.substring(i);
}
发布于 2012-07-15 15:48:39
找到索引后,即使它是-1,也只需要将从index + 1
(因为索引是最后一个匹配的字符索引)到字符串末尾的子字符串追加到原始字符串。String中有一个方法可以获取这个子字符串。
https://stackoverflow.com/questions/11490290
复制相似问题