KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,它可以在O(n)时间内完成字符串的匹配。在这个问题中,我们将使用KMP算法来检测一个字符串是否是回文串。回文串是指正读和反读都相同的字符串。
以下是使用Java实现基于KMP算法的回文串检测的步骤:
public static int[] buildPrefixFunction(String pattern) {
int[] prefixFunction = new int[pattern.length()];
int len = 0;
int i = 1;
while (i < pattern.length()) {
if (pattern.charAt(i) == pattern.charAt(len)) {
len++;
prefixFunction[i] = len;
i++;
} else {
if (len != 0) {
len = prefixFunction[len - 1];
} else {
prefixFunction[i] = 0;
i++;
}
}
}
return prefixFunction;
}
public static boolean isPalindrome(String s) {
if (s == null || s.length() == 0) {
return true;
}
int[] prefixFunction = buildPrefixFunction(s);
int left = 0;
int right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left += prefixFunction[left];
right -= prefixFunction[right];
}
return true;
}
public static void main(String[] args) {
String test1 = "abccba";
String test2 = "abcddcba";
String test3 = "hello";
System.out.println("Test 1: " + isPalindrome(test1)); // Output: true
System.out.println("Test 2: " + isPalindrome(test2)); // Output: true
System.out.println("Test 3: " + isPalindrome(test3)); // Output: false
}
这个实现首先构建了一个前缀函数,然后使用KMP算法检测字符串是否是回文串。在测试用例中,我们可以看到前两个字符串是回文串,而第三个字符串不是。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。