<= size1 - size2;++i){if (needleFingerprint == haystackFingerprint){return i;}haystackFingerprint = (2 * haystackFingerprint - static_cast(pow(2, size2))* haystack[i]+ haystack[i + size2]) % mod;}return -1;}//Las Vegas算法，从文本串haystack中找到模式串needle第一次出现的位置int subStringLV(string haystack, string needle){int size1 = haystack.size();int size2 = needle.size();if (size2 == 0) return 0;long long needleDecimal = binaryToDecimal(needle);long long haystackDecimal = binaryToDecimal(haystack.substr(0, size2));int needleFingerprint = getFingerprint(needleDecimal);int haystackFingerprint = getFingerprint(haystackDecimal);for (int i = 0;i <= size1 - size2;++i){if (needleFingerprint == haystackFingerprint){int j;for (j = 0; haystack[i + j] == needle[j] && j < size2; ++j);if (j == size2) return i;}haystackFingerprint = (2 * haystackFingerprint - static_cast(pow(2, size2))* haystack[i]+ haystack[i + size2]) % mod;}return -1;}int main(){//文本串数组vector haystacks(10000);//模式串数组vector needles(10000);//初始化srand(time(0));for (int i = 0;i < 10000;++i){for (int j = 0;j < 500;++j){haystacks[i].push_back((rand() % 2) + '0');}for (int k = 0;k < 50;++k){needles[i].push_back((rand() % 2) + '0');}}//KMP算法vector result1(10000); //存储10000对字符串的匹配结果clock_t start1 = clock();for (int i = 0;i < 10000;++i){result1.emplace_back(subStringKMP(haystacks[i], needles[i]));}clock_t finish1 = clock();double duration1 = static_cast(finish1 - start1);cout << "KMP算法的运行时间为: " << duration1 << "毫秒" << endl;//Monte Carlo算法vector result2(10000); //存储10000对字符串的匹配结果clock_t start2 = clock();for (int i = 0;i < 10000;++i){result2.emplace_back(subStringMC(haystacks[i], needles[i]));}clock_t finish2 = clock();double duration2 = static_cast(finish2 - start2);cout << "Monte Carlo算法的运行时间为: " << duration2 << "毫秒" << endl;//Las Vegas算法vector result3(10000); //存储10000对字符串的匹配结果clock_t start3 = clock();for (int i = 0;i < 10000;++i){result3.emplace_back(subStringLV(haystacks[i], needles[i]));}clock_t finish3 = clock();double duration3 = static_cast(finish3 - start3);cout << "Las Vegas算法的运行时间为: " << duration3 << "毫秒" << endl;int count = 0;for (int i = 0;i < 10000;++i){if (result1[i] == result2[i]){++count;}}double accuracy = count / 10000;cout << "Monte Carlo算法的准确率为:" << accuracy * 100 << "%" << endl;bool flag = (result1 == result3);if (flag){cout << "Las Vegas算法正确" << endl;}return 0;}
6.时间复杂度
KMP: O(size1 + size2)
Monte Carlo: O(size1 + size2)
Las Vegas: O(size1 + size2)
7.结论
随机数P应当取一个较大的质数 。当P一定大时，Monte Carlo算法的出错率要比1/size1小得多。而Las Vegas算法一定正确 。
