在一个大字符串中寻找子串的两种实现方法

第一种是使用一个点进行查找的方式，以下是实现的代码。

bool findSub1(string  scr, string tar)
{using namespace std;if (scr.empty() || tar.empty() || scr.size() < tar.size())return false;for (int i = 0; i < scr.size(); i++){int temp = i;if (scr[i] == tar[0]){int j;for (j = 1, i = temp + 1; j < tar.size(), i < (temp + tar.size()); j++, i++){if (scr[i] != tar[j])break;}if (j == tar.size())return true;}}return false;
}

我们还可以使用两个监测点相距一个tar.size()的方式进行查找，以下是代码。

bool findSub2(string scr, string tar)
{using namespace std;if (scr.empty() || tar.empty() || scr.size() < tar.size())return false;int i, j;for (i = 0, j = tar.size() - 1; i < (scr.size() - tar.size()), j < scr.size(); i++, j++){if (scr[i] == tar[0] && scr[j] == tar[tar.size() - 1]){int m = 1;int k = i + 1;while (k < j) //k and m are syncronized{if (scr[k] != tar[m])break;k++; m++;}if (k == j) //since in the last loop, 1 is still added to kreturn true;}}return false;
}

虽然两套代码长相不同，但是逻辑上还是没有逃过对每一个元素进行遍历的本质。其实偷懒一点的方法是直接使用头文件cstring下的string scr.find(string tar, 0)。第二个参数是要查找的起始位置。但是动动脑子多想几种办法总之是对编程能力提升有好处的。

第一次写这东西，初衷是想记录一下自己的计算机学习历程，当然我也希望我的内容能够给各位看官提供一点帮助。