文字列検索アルゴリズムのSunday

SUNDAYアルゴリズムの説明:
文字列検索アルゴリズムの中で最も有名な2つはKMPアルゴリズム(Knuth-Morris-Pratt)とBMアルゴリズム(Boyer-Moore)である.両方のアルゴリズムは、最悪の場合、線形の検索時間を有する.しかし、実用的には、KMPアルゴリズムは最も簡単なcライブラリ関数strstr()よりもそれほど速くないが、BMアルゴリズムはKMPアルゴリズムより3〜5倍速いことが多い.しかし、BMアルゴリズムはまだ最も速いアルゴリズムではありません.ここでは、BMアルゴリズムよりも速い検索アルゴリズムを紹介します.
たとえば、「substring searching algorithm」で「search」を検索し、最初はテキストの左側にサブ列を揃えます.
substring searching algorithm search ^
その結果、2番目の文字に不一致が見つかり、サブストリングを後ろに移動します.でもどれくらい移動すればいいですか?これは様々なアルゴリズムがそれぞれ神通力を示している場所で、最も簡単な方法は1つの文字の位置を移動することです.KMPは、マッチングされた部分の情報を利用して移動する.BMアルゴリズムは逆比較を行い,一致した部分に基づいて移動量を決定する.ここで紹介する方法は、現在のサブストリングの直後にある文字(上図の'i')を見ることです.
明らかに、いくら移動しても、この文字は次の比較に参加するに違いありません.つまり、次のステップが一致した場合、この文字はサブストリング内にある必要があります.したがって、サブストリングを移動して、サブストリングの右端のこの文字を位置合わせすることができます.現在、サブストリング'search'には'i'が存在しない場合は、大きなブロックを直接スキップできることを示し、'i'の後の文字から次のように比較します.
substring searching algorithm 　　　 search 　　　　^
比較の結果、最初の文字は一致せず、サブストリングの後ろの文字を見ると、「r」であり、サブストリングの中で最後から3番目に現れ、サブストリングを3桁前に移動し、2つの「r」を位置合わせします.以下のようにします.
substring searching algorithm 　　　　 search 　　　　　　　^
ああ!今回のマッチングは成功しました!全体の過程を振り返ると、私たちは2人の次男串だけを移動してマッチング位置を見つけましたが、神様ではないでしょうか?!このアルゴリズムでは,ステップ毎の移動量がBMアルゴリズムよりも大きいので,BMアルゴリズムよりも速いに違いないことが実証された.
 
コードは次のとおりです.
 

const char* sunday(const char* str, const char* subStr)
{
	const int maxSize=256;
	int next[maxSize];
	int strLen = strlen(str);
	int subLen = strlen(subStr);
	int i,j,pos;
	for(i=0;i<maxSize;i++)
	{
		next[i] = subLen+1;
	}
	for(i=0;i<subLen;i++)
	{
		next[ (unsigned char)subStr[i] ] = subLen-i;//               \0     
	}
	pos=0;
	while(pos<=(strLen-subLen))
	{
		i=pos;
		for(j=0;j<subLen;j++,i++)
		{
			
			if(str[i] != subStr[j])
			{
				pos += next[ (unsigned char)str[pos+subLen] ];//    
				break;
			}
			
		}
		if(j==subLen)//    ，  
		{
			return str+pos;
		}
	}
	return NULL;
}