java字符串算法题 Java 字符串算法

java字符串算法题

Java字符串算法是一种基于字符串的数据结构和算法，它可以帮助我们解决一些关于字符串的问题。Java字符串算法可以用来搜索、替换、分割、合并、排序和匹配字符串，这些都是在处理字符串时常用的操作。

Java中有许多不同的字符串处理方法，但是最常用的就是KMP(Knuth-Morris-Pratt) 算法。KMP 算法是一种快速的子字符串匹配方法，它可以在O(n)时间内找到子字符串在目标字符串中出现的位置。KMP 的原理是使用一个“部分匹配表”来跳过不必要的匹配，从而大大减少了时间复杂度。

public static int kmpSearch(String str, String pattern) {
    int[] next = getNext(pattern); // 获取部分匹配表
    int i = 0; // 主串的位置
    int j = 0; // 模式串的位置

    while (i < str.length() && j < pattern.length()) {
        if (j == -1 || str.charAt(i) == pattern.charAt(j)) { // 当j=-1时，要采用str.charAt(i) == pattern.charAt(0)来判断，而不是str.charAt(i) == pattern.charAt(-1) 
            i++; 
            j++; 
        } else {  // 当前字母不匹配，则j回退 
            j = next[j];   // j回到next[j]处开始重新匹配 
        } 
    }

    if (j == pattern.length()) {   // 判断是否找到子字符串 
        return i - j;   // 返回子字
Java 字符串算法
Java数据类型教程 -  Java字符串算法

测试字符串的Palindrome
回文是一个单词，一个诗句，一个句子或一个在前后方向上相同的数字。
以下代码显示了如何检查字符串是否是回文。
public class Main {
  public static void main(String[] args) {
    String str2 = "noon";
    System.out.println(isPalindrome(str2));
  }
  public static boolean isPalindrome(String inputString) {
    int len = inputString.length();
    if (len <= 1) {
      return true;
    }
    String newStr = inputString.toUpperCase();
    boolean result = true;
    int counter = len / 2;
    for (int i = 0; i < counter; i++) {
      if (newStr.charAt(i) != newStr.charAt(len - 1 - i)) {
        result = false;
        break;
      }
    }
    return result;
  }
}
上面的代码生成以下结果。