java字符串搜索算法 Java 字符串搜索

java字符串搜索算法

Java字符串搜索算法是一种用于在字符串中搜索特定子串的算法。它可以帮助开发人员快速找到特定的子串，从而更好地处理字符串。

Java字符串搜索有很多不同的方法，其中最常用的是KMP（Knuth-Morris-Pratt）和Boyer-Moore（BM）。KMP是一种基于模式匹配的字符串搜索方法，它使用一个“跳表”来跳过不必要的匹配步骤。Boyer-Moore则是一种基于文本匹配的字符串搜索方法，它使用一个“坏字表”来跳过不必要的匹配步骤。

KMP 算法是一个时间复杂度 O(m+n) 的有效搜索方法，其中 m 是目标字符串的长度，n 是要搜寻的子字符串的长度。KMP 算法通过分析目标字符串和子字符串之间的差异来减少不必要的匹配步骤。

public static int kmpSearch(String text, String pattern) { 
    int n = text.length(); 
    int m = pattern.length(); 

    // 创建 lps[] 数组 
    int[] lps = new int[m]; 

    // 计算 lps[] 数组 
    computeLPSArray(pattern, m, lps); 

    int i = 0; // index for txt[] 
    int j = 0; // index for pat[] 

    while (i < n) { 

        if (text.charAt(i) == pattern.charAt(j)) { 

            i++; j++; 

            if (j == m) { // 子字符串已找到  
                return i - j;  

                j = lps[j - 1];  
            }  

        } else { // 子字
Java 字符串搜索
Java数据类型教程 -  Java字符串搜索

我们可以使用indexOf()和lastIndexOf()方法获取另一个字符串中的字符或字符串的索引。例如
public class Main {
  public static void main(String[] args) {
    String str = new String("Apple");

    int index = str.indexOf("p"); // index will have a value of 1
    System.out.println(index);
    
    index = str.indexOf("pl"); // index will have a value of 2
    System.out.println(index);
    index = str.lastIndexOf("p"); // index will have a value of 2
    System.out.println(index);
    
    index = str.lastIndexOf("pl"); // index will have a value of 2
    System.out.println(index);
    
    index = str.indexOf("k"); // index will have a value of -1
    System.out.println(index);
  }
}
上面的代码生成以下结果。
indexOf()方法从字符串的开头开始搜索字符或字符串，并返回第一个匹配的索引。
lastIndexOf()方法从末尾匹配字符或字符串，并返回第一个匹配的索引。
如果在字符串中没有找到字符或字符串，这些方法返回-1。

匹配字符串的开始和结束
startsWith()检查字符串是否以指定的参数开头，而endsWith()检查字符串是否以指定的字符串参数结尾。
两个方法都返回一个布尔值。
public class Main {
  public static void main(String[] args) {
    String str = "This is a test";

    // Test str, if it starts with "This"
    if (str.startsWith("This")) {
      System.out.println("String starts with  This");
    } else {
      System.out.println("String does  not  start with  This");
    }

    // Test str, if it ends with "program"
    if (str.endsWith("program")) {
      System.out.println("String ends  with  program");
    } else {
      System.out.println("String does  not  end  with  program");
    }

  }
}
上面的代码生成以下结果。