java indexof（String str）方法复杂度

可能重复：
String.indexof（）函数调用的成本/复杂性是多少？

java indexof（String str）方法的复杂性是什么？ 我的意思是有像KMP这样的字符串匹配算法，它们在线性时间内运行。 我正在实现一个需要在一个非常大的字符串中搜索大子字符串的系统，所以我可以使用java indexof（String str）方法，或者我应该实现KMP。

Answer 1

Java 实现 indexOf的复杂性是O(m*n) ，其中n和m分别是搜索字符串和模式的长度。

你可以做的是提高复杂性，例如，使用Boyer-More算法智能地跳过比较字符串中与模式不匹配的逻辑部分。

Answer 2

java indexOf函数复杂度为O(n*m) ，其中n是文本的长度，m是模式的长度
这里是indexOf原始代码

  /** * Returns the index within this string of the first occurrence of the * specified substring. The integer returned is the smallest value * k such that: * 
 * this.startsWith(str, k) * 

 * is true. * * @param str any string. * @return if the string argument occurs as a substring within this * object, then the index of the first character of the first * such substring is returned; if it does not occur as a * substring, -1 is returned. */ public int indexOf(String str) { return indexOf(str, 0); } /** * Returns the index within this string of the first occurrence of the * specified substring, starting at the specified index. The integer * returned is the smallest value k for which: * 

 * k >= Math.min(fromIndex, this.length()) && this.startsWith(str, k) * 

 * If no such value of k exists, then -1 is returned. * * @param str the substring for which to search. * @param fromIndex the index from which to start the search. * @return the index within this string of the first occurrence of the * specified substring, starting at the specified index. */ public int indexOf(String str, int fromIndex) { return indexOf(value, offset, count, str.value, str.offset, str.count, fromIndex); } /** * Code shared by String and StringBuffer to do searches. The * source is the character array being searched, and the target * is the string being searched for. * * @param source the characters being searched. * @param sourceOffset offset of the source string. * @param sourceCount count of the source string. * @param target the characters being searched for. * @param targetOffset offset of the target string. * @param targetCount count of the target string. * @param fromIndex the index to begin searching from. */ static int indexOf(char[] source, int sourceOffset, int sourceCount, char[] target, int targetOffset, int targetCount, int fromIndex) { if (fromIndex >= sourceCount) { return (targetCount == 0 ? sourceCount : -1); } if (fromIndex < 0) { fromIndex = 0; } if (targetCount == 0) { return fromIndex; } char first = target[targetOffset]; int max = sourceOffset + (sourceCount - targetCount); for (int i = sourceOffset + fromIndex; i <= max; i++) { /* Look for first character. */ if (source[i] != first) { while (++i <= max && source[i] != first); } /* Found first character, now look at the rest of v2 */ if (i <= max) { int j = i + 1; int end = j + targetCount - 1; for (int k = targetOffset + 1; j < end && source[j] == target[k]; j++, k++); if (j == end) { /* Found whole string. */ return i - sourceOffset; } } } return -1; } 

 您可以在不使用indexOf情况下简单地实现KMP算法 
 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.Scanner; public class Main{ int failure[]; int i,j; BufferedReader in=new BufferedReader(new InputStreamReader(System.in)); PrintWriter out=new PrintWriter(System.out); String pat="",str=""; public Main(){ try{ int patLength=Integer.parseInt(in.readLine()); pat=in.readLine(); str=in.readLine(); fillFailure(pat,patLength); match(str,pat,str.length(),patLength); out.println(); failure=null;}catch(Exception e){} out.flush(); } public void fillFailure(String pat,int patLen){ failure=new int[patLen]; failure[0]=-1; for(i=1;i=0&&pat.charAt(j+1)!=pat.charAt(i)) j=failure[j]; if(pat.charAt(j+1)==pat.charAt(i)) failure[i]=j+1; else failure[i]=-1; } } public void match(String str,String pat,int strLen,int patLen){ i=0; j=0; while(i