字符串匹配算法之 KMP

• 暴力破解版

/** 
* 
* @param source 母串 
* @param pattern 字串 
* @return 返回第一个匹配子串的头部位置,没有匹配返回-1 
*/
public static int violentMatcher(String source, String pattern){ 
   //获得两个字符串的长度  
   int slen = source.length();  
   int plen = pattern.length();   
   if(slen == 0)      
     return -1;   
   if(plen == 0)      
     return -1;   

   char [] sc = source.toCharArray();    
   char [] pc = pattern.toCharArray();   
   int i = 0;   
   int j= 0;   

   while (i< slen && j < plen){//j == plen 跳出循环，就找到子串       
     if(sc[i] == pc[j]){//匹配相等，都+1         
       j++;         
       i++;       
     } else {//不相等i退回j个位置再+1，j重置0        
       i=i-j+1;        
       j=0;        
     }    
   }  
  if(j == plen)     
    return i - plen;    
  else    
    return -1;
}

• KMP版

/**
 * KMP 算法：分两个阶段，
 * 1.预处理求子串的next数组. 
 * 2.根据next数组，在不匹配时，后移相应的位数(不是暴力破解的每次后移一位)
 * @param source
 * @param pattern
 * @return
 */
public static int KMPMatcher(String source, String pattern){ 
    //获得两个字符串的长度  
    int slen = source.length()
    int plen = pattern.length();
    if(slen == 0)
        return -1;
    if(plen == 0)
        return -1;

    char [] sc = source.toCharArray();
    char [] pc = pattern.toCharArray();
    int i = 0;
    int j= 0;

    int[] next = getNext(pc); // 获得next数组

    while(i< slen && j < plen){//j == plen 跳出循环，就找到子串
        if(sc[i] == pc[j]){//匹配相等，都+1
            j++;
            i++;
        }
        else {//不相等 子串右移j-next[j]
            j = next[j];
        }
    }
    return 0;
}

//找出字符串前缀和后缀，最长的共有元素个数
private static int [] getNext(char[] s){
    int q=0,k=-1; // char数组的下标， k 最大前后缀的相同长度
    int[] next = new int[s.length];
    next[0] = -1;
    while (q < s.length-1){
        if(k == -1 || s[q] == s[k]){
            q++;
            k++;
            next[q] = k;
        }else {
            k = next[k];
        }
    }
    next[0] = 0;
    return next;
}

• Boyer-more算法