Java实现字符串匹配算法KMP，java字符串算法kmp,kmp算法的核心思想：先

Java实现字符串匹配算法KMP，java字符串算法kmp,kmp算法的核心思想：先

kmp算法的核心思想：先对搜索字串生成偏移对照表，匹配时从左向右依次比较（bm从右向左，号称比kmp更快），相等则文档和搜索字串的下标+1迭代，否则查表，定位最优的偏移位置（文档下标不变，搜索字串下标改变）。例外是，字符不匹配时，若搜索字串的下标为0，则文档的下标+1，继续迭代比较。import java.util.Arrays; public class KMPSearch { public static int[] table; public static void generateTab(String key){//查询字串生成偏移对照表，一次迭代就可以 int len=key.length(); table=new int[len]; Arrays.fill(table, 0); for(int i=1;i<len;i++){ if(key.charAt(i)==key.charAt(table[i-1])){ table[i]=table[i-1]+1; } } for(int v : table){ System.out.print(v); } System.out.println(); } public static int KMPSearchs(String doc,String key){ generateTab(key); int result=-1; int doc_size=doc.length(), key_size=key.length(), doc_iter=, key_iter=; while(doc_iter<doc_size){//遍历所查询的文档，同样，单层循环就可以实现→_→ if(doc.charAt(doc_iter)==key.charAt(key_iter)){ doc_iter++; key_iter++; }else{ if(key_iter==0){ doc_iter++; continue; }else{ key_iter=table[key_iter-1]; continue; } } if(key_iter==key_size){ result=doc_iter-key_size; break; } } return result; } public static void main(String[] args){ int i=KMPSearchs("bbc abcdab abcdabcdabde","abcdabd"); System.out.println(i); } } ```java import java.util.Arrays;

public class KMPSearch {      public static int[] table;      public static void generateTab(String key){//查询字串生成偏移对照表，一次迭代就可以          int len=key.length();          table=new int[len];          Arrays.fill(table, 0);        for(int i=1;i<len;i++){              if(key.charAt(i)==key.charAt(table[i-1])){                  table[i]=table[i-1]+1;              }          }          for(int v : table){              System.out.print(v);          }          System.out.println();      }      public static int KMPSearchs(String doc,String key){          generateTab(key);          int result=-1;          int doc_size=doc.length(),              key_size=key.length(),              doc_iter=0,              key_iter=0;          while(doc_iter<doc_size){//遍历所查询的文档，同样，单层循环就可以实现→_→              if(doc.charAt(doc_iter)==key.charAt(key_iter)){                  doc_iter++;                  key_iter++;              }else{                  if(key_iter==0){                      doc_iter++;                      continue;                  }else{                      key_iter=table[key_iter-1];                      continue;                  }              }              if(key_iter==key_size){                  result=doc_iter-key_size;                  break;              }          }          return result;      }      public static void main(String[] args){          int i=KMPSearchs("bbc abcdab abcdabcdabde","abcdabd");          System.out.println(i);      }  }

```