Java實現Sunday百萬級數據量的字元串快速匹配演算法

    背景

      在平時的項目中,幾乎都會用到比較兩個字元串時候相等的問題,通常是用==或者equals()進行,這是在數據相對比較少的情況下是沒問題的,當資料庫中的數據達到幾十萬甚至是上百萬千萬的數據需要從中進行匹配的時候,傳統的方法顯示是不行的,影響匹配的效率,時間也會要很久,用戶體驗很差的,今天就要介紹一種字元串匹配的演算法Sunday。接下來就詳細介紹了

     Sunday演算法是Daniel M.Sunday於1990年提出的字元串模式匹配。其核心思想是：在匹配過程中，模式串發現不匹配時，演算法能跳過儘可能多的字元以進行下一步的匹配，從而提高了匹配效率。相比於另外幾個著名的字元串匹配演算法，KMP以及BM演算法而言，Sunday演算法不僅理解起來比較容易，而且往往能有更好的速度。
   

     首先i,j兩個指針指示的位置（也就是從頭開始匹配），當發現失配的時候就判斷子串的後一位在母串的字元即空格（k標記處）是否在子串中存在？如果存在則將該位置和子串中的該字元對齊，在從頭開始匹配。如果不存在就將子串向後移動，和母串k+1處的字元對齊，再進行匹配。重覆上面的操作直到找到，或母串被找完結束。

  

　　如上圖，這次比較還是失配，但是k位置的e在子串中出現了，而且第一個就是，最後一個也是，這時候一定要將子串中靠後出現的e和母串中的e對齊如下圖。 

再從i,j開始進行比較。。。。。 
代碼如下

package per.zh.tess4j;

/***
* 字元串快速匹配sunday演算法
* sunday與horspool優於strstr、BM、KMP，BM匹配速度相當於KMP的三倍。
* (1)strstr():c語言的庫函數
* (2)KMP(Knuth-Morris-Pratt)演算法
* (3)BM(Boyer-Moore)演算法
* (4)Horspool演算法
* (5)Sunday演算法
* @author lenovo
* @date 2019年3月22日
* description:
*/
public class SundayTest {

　　public static void main(String[] args) {
　　　　String s="abcdebcdbcdegbcde";
　　　　String p="bcdeg";
　　　　Sunday(s, p);

　　}

　　//註意每次都是從後向前
　　public static int contains(char[] str,char ch){
　　　　for(int i=str.length-1;i>=0;i--){
　　　　　　if(str[i]==ch){
　　　　　  　return i;
　　　　　　}
　　　　}
　　　　return -1;
　　}

　　/**
　　* 匹配字元串
　　* @param s 目標字元串
　　* @param p 需要匹配的字元串
　　*/

　　public static void Sunday(String s,String p){
　　　　char[] sarray = s.toCharArray();
　　　　char[] parray = p.toCharArray();
　　　　int slen=s.length();
　　　　int plen=p.length();
　　　　int i=0,j=0;
　　　　while(i<=slen-plen+j){//這句話控制索引i,j的範圍
　　　　　　if(sarray[i]!=parray[j]){//假如主串的sarry[i]與模式串的parray[j]不相等
　　　　　　if(i==slen-plen+j){
　　　　　　　　break;//假如主串的sarry[i]與模式串的parray[j]不相等,並且i=slen-plen+j,說明這已經
　　　　　　　　//是在和主串中最後可能相等的字元段比較了,並且不相等,說明後面就再也沒有相等的了,所以
　　　　　　　　//跳出迴圈,結束匹配
　　　　　　}
　　　　　　//假如是主串的中間欄位與模式串匹配，且結果不匹配
　　　　　　//則就從模式串的最後面開始,(註意是從後向前)向前遍歷,找出模式串的後一位在對應的母串的字元是否在子串中存在
　　　　 int pos=contains(parray, sarray[i+plen-j]);
　　　 　if(pos==-1){//表示不存在
　　　　　 　i=i+plen+1-j;
　　　　　 　j=0;
　　　 　}else{
　　　　　　i=i+plen-pos-j;
　　　　　　j=0;
　　　　}
　　 }else{//假如主串的sarry[i]與模式串的parray[j]相等,則繼續下麵的操作
 　　　　　　if(j==plen-1){//判斷模式串的索引j是不是已經到達模式串的最後位置，
　　　　　　　　//j==plen-1證明在主串中已經找到一個模式串的位置,
　　　　　　　　//且目前主串尾部的索引為i,主串首部的索引為i-j,列印模式串匹配的第一個位置
　　　　　　　　System.out.println("the start pos is "+(i-j)+" the end pos is "+i);
　　　　　　　　//然後主串右移一個位置,再和模式串的首字元比較,從而尋找下一個匹配的位置
　　　　　　　　i=i-j+1;
　　　　　　　　j=0;
　　　　　　}else{
　　　　　　　　//假如模式串的索引j!=plen-1,說明模式串還沒有匹配完,則i++,j++繼續匹配,
　　　　　　　　i++;
　　　　　　　　j++;
　　　　　　}
　　　　}
　　 }
　}