Sunday算法模板

Sunday算法由Daniel M.Sunday在1990年提出，它的思想跟BM算法很相似：1
只不过Sunday算法是从前往后匹配，在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符。
如果该字符没有在模式串中出现则直接跳过，即移动位数 = 模式串长度 + 1；
否则，其移动位数 = 模式串长度 - 该字符最右出现的位置(以0开始) = 模式串中该字符最右出现的位置到尾部的距离 + 1。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
string s,p;
int next_[257];
void getnext(){
	int len=p.size();
	for(int i=0;i<256;i++)next_[i]=-1;
	for(int i=0;i<len;i++)next_[p[i]]=i;   //打next_表，记录模式串相应字符的位置 
}
int sunday(){
	int slen=s.size();
	int plen=p.size();
	if(slen==0)return -1;		//如果s的长度为0，不需要匹配，直接返回-1 
	for(int i=0;i<slen-plen;){
		int j=i;	//s[j] 
		int k=0;	//p[k]
		for(;k<plen&&j<slen&&s[j]==p[k];j++,k++);//一直匹配，找到失配 j 和  k 
		if(k==plen)	//说明已经找到一段匹配串
			return i;	//如果要查找出现次数，改成cnt++
		else{
			if(i+plen<slen)i+=(plen-next_[s[i+plen]]);
			else return -1;//	//如果要查找出现次数，改成return cnt
		} 
	}
	return -1;
}
int main(){
	s="I love DNF and Code";
	p="love";
	getnext();
	if(sunday())printf("you find it at %d\n",sunday());
	else printf("sorry,you do not find it!\n");
	
}