Sunday算法

        查找字元串問題經久不衰。最普通的BF樸素查找算法，在目标串中查找子串，按位置查找，查找出錯則傳回目标串開始查找位置的下一位置繼續查找。該算法是最簡單但是效率最低的。複雜度m*n。

        kmp算法維護一個查找數組，通過該數組在查找失敗的時候确定子串下次比較的位置。參考文章：https://blog.csdn.net/qq_38701476/article/details/81512525

         bm算法通過壞字元與好字尾确定比對失敗時子串移動的位置。他一般有兩個規則，1、出現壞字元的時候，如果子串中存在該字元，則将母串中該字元與子串裡最右邊字元與其對其。如果不存在，則整片跳過。2、出現好字尾的時候，如果子串中存在，則将母串中好字尾與子串中最右邊好字尾對其。如果不存在，整片跳過。參考文章：http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html

        sunday算法，相比kmp和bm算法了解起來就容易得多。核心思想便是盡可能的跳過不需要比較的區域。目标串與子串從左向右移動，但是從右向左比較，當比較失敗的時候，确定母串中該字元是否在子串存在，存在則移動到該字元的位置，不存在則整片跳過。

母串：1    3    4    5    6    7    8

子串：5    9    9    6

        母串與子串進行比較，從右向左。5與6比較失敗，子串中存在5，則子串中的5與母串中5對其。如果不存在，則子串中5與母串中7對齊。

void sunday_test()
{
	string strSrc = "qwyrjshdfwe7234gqyerb23bhufebhu";
	string strDes = "bhu";
	int iLenSrc = strSrc.length();
	int iLenDes = strDes.length();

	vector<int> veNext;
	for (int i = 0; i < 256; ++i)
		veNext.push_back(iLenDes + 1);
	for (int i = 0; i < iLenDes; ++i)
		veNext[strDes[i]] = iLenDes - i;

	for (int i = 0; i < iLenSrc - iLenDes; i += veNext[strSrc[i + iLenDes]])
	{
		int j = 0;
		while (j < iLenDes)
		{
			if (strSrc[i + j] != strDes[j])
				break;
			++j;
		}
		if (j == iLenDes)
		{
			cout << "pos: " << i << endl;
		}
	}
}