Sunday算法
匹配原理
从前往后匹配，如果遇到不匹配情况，则查看母串S中参与匹配的最后一位的下一位字符，记做C，如果C出现在模板串T中，选择模板串中C最右出现的位置对齐；如果C没有出现在模板串T中，直接跳过该匹配区域。
算法演示
母串S： S E A R C H S U B S T R I N G
模板串T：S U B S T R I N G
开始匹配：
开始匹配.png
匹配成功，开始下一次匹配：
下一次匹配.png
匹配失败：
查找母串S参与匹配的最后一位字符的下一字符，基黄色的S；
在T中，字符’S’出现两次，按照原理，选择T中最右位置出现的’S’进行对齐，那么可以得到：
匹配失败.png
假设母串S为：S E A R C H S U B Z T R I N G
那么当匹配到上述情况时，字符’Z’在T中没有出现，那么就可以得到下面的情况：
匹配失败.png
可以看到，当匹配失败时，跳过的区域很大。
代码如下:
/**
*
* @param S 母串
* @param T 模式串
* @return
*/
static int sunday(String S, String T){
int[] moveLen = getMoveLength(T);
int i=0; // S 下标
int j =0;// T 下标
while (j<T.length() && i<S.length()){
for(j=0; j<T.length() && i+j <S.length() && S.charAt(i+j)==T.charAt(j); ++j) ;
// 匹配成功
if(j == T.length()) return i;
// S中没有找到含T的字符串
if(i+T.length() >= S.length()) return -1;
//移动S的索引
i += moveLen[S.charAt(i+T.length())];
}
return -1;
}
static int[] getMoveLength(String T){
int[] moveLen = new int[256]; // 字符的种类数目
// 默认S中的任何字符均不出现在T中，那么每次移动的距离为T的长度 + 1
for(int i=0; i<moveLen.length; ++i){
moveLen[i] = T.length() + 1;
}
//查找能够出现在T中的字符，若一个字符出现多次，选择最右位置的字符，所以T的下标遍历从0开始
for(int i=0; i<T.length(); i++){
moveLen[T.charAt(i)] = T.length() - i;
}
}
