简介

Daniel M.Sunday于1990年提出的字符串模式匹配。其效率在匹配随机的字符串时比其他匹配算法还要更快，同时其实现方式比KMP，BM的实现容易太多。

 

算法原理

作为一个字符串模式匹配算法，Sunday算法的核心在于通过跳过尽可能多的字符来提高匹配效率，此处如何跳过尽可能多的字符串是本算法的核心思想。

举例：

在字符串this is a big city（母串）中查找city（字串）字符串

A

t

h

i

s

i

s

a

b

i

g

c

i

t

y

B

c

i

t

y

1.第一次查找

将字串与母串开始进行比较，结果显示不匹配。接下来按照sunday算法规则，将母串中的未与字串进行匹配的首个字符（即第五个字符）在字串中进行查找（在例子中即在B串中查找字符i）此时会出现两种情况，即找到和未找到，例子中的情况是找到，则将字串整个向后移动至两个i位置对齐，如图所示：

A

t

h

i

s

i

s

a

b

i

g

c

i

t

y

B

c

i

t

y

2.第二次查找

情况与第一次不同，在B串中没有找到字符b，因此直接将B串向后移动它自身长度的位数，移动后结果：

A

t

h

i

s

i

s

a

b

i

g

c

i

t

y

B

c

i

t

y

3.第三次查找

结果依然不匹配，但是在进行母串中的未与字串进行匹配的首个字符（即第五个字符）在字串中进行查找时出现了找到的情况，此时依据找到的字符移动字串，结果需要字串中的最右的该字符与母串中的字符位置相对应，结果如下图：

A

t

h

i

s

i

s

a

b

i

g

c

i

t

y

B

c

i

t

y

 

Java代码实现：

package Sunday;
/***@author JDK9*@date 2017-4-6*@description SunDay算法代码实现**/
public class SundayUtil {public String sunday(String sourse, String target) {String retVal="";char[] tempS = sourse.toCharArray();char[] tempT = target.toCharArray();int k=0;int j=0;if(compare(tempS,tempT,k,j)){retVal = "查找成功"; }else{retVal = "查找完成，未找到"; }return retVal;}/*** 对比主过程(递归调用)* @param tempS 源字符串* @param tempT 目标字符串* @param j 本次比较源字符串初始下标* @param k 同j* @return*/public boolean compare(char[] tempS, char[] tempT, int j, int k) {System.out.println("比较开始下标："+k+"  "+j);for(int i=j;i<j+tempT.length;i++){if(tempT[i-j]==tempS[i]){k++;continue;}else{break;}}//k-j代表本次比较的次数，如果和目标字符串的长度相等，则说明每个字符都对比成功，即在源字符串中找到了目标字符串if(k-j==tempT.length){System.out.println("匹配成功");return true;}k=j+tempT.length;if(k<(tempS.length-1)){int value = check(tempS[k],tempT);int step = -value;j=k+step;return compare(tempS,tempT,j,j);}else{return false;}}/*** 检查目标字符串tempT是否包含c* @param c* @param tempT* @return*/public int check(char c, char[] tempT) {for(int i = tempT.length-1;i>=-1;i--){if(i==-1||tempT[i]==c){return i;}else{continue;}}return 0;}}