本文为senlie原创，转载请保留此地址：

search

-------------------------------------------------------------------------

描写叙述：在序列一[first1, last1) 所涵盖的区间中。查找序列二[first2, last2) 的首次出现点。

思路：

1.遍历序列二

2.假设两序列的当前元素一样，都前进 1

3.否则序列二的迭代器又一次指向開始元素，序列一前进 1 ，序列一的长度减 1

复杂度：

最坏情况是平方: 最多 (last1 - first1) * (last2 - first2) 次比較。 但最坏情况非常少出现。

平均情况下是线性复杂度

源代码：

template 
     
      inline ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,                               ForwardIterator2 first2, ForwardIterator2 last2){  return __search(first1, last1, first2, last2, distance_type(first1),                  distance_type(first2));}//没看源代码之前，还以为会有什么复杂的算法。结果也仅仅是遍历//假设没有假设(比方有序什么的)，STL里的很多算法实现也是挺普通的做法template 
      
       ForwardIterator1 __search(ForwardIterator1 first1, ForwardIterator1 last1,                          ForwardIterator2 first2, ForwardIterator2 last2,                          Distance1*, Distance2*) {  Distance1 d1 = 0;  distance(first1, last1, d1);  Distance2 d2 = 0;  distance(first2, last2, d2);  if (d1 < d2) return last1; //假设第二序列大于第一序列，不可能成为其子序列  ForwardIterator1 current1 = first1;  ForwardIterator2 current2 = first2;  while (current2 != last2) // 我的第一感觉是遍历第一序列。结果人家是遍历第二序列。只是感觉代码写起来应该差点儿相同    if (*current1 == *current2) { // 假设这个元素同样。调整，以便比对下一个元素      ++current1;      ++current2;    }    else { //假设这个元素不同      if (d1 == d2) //假设两序列一样长了。就不可能成功了        return last1;      else { //假设两序列不一样长，调整序列标兵        current1 = ++first1;        current2 = first2;        --d1; //已经排序了序列一的一个元素。所以序列一的长度要减 1      }    }  return first1;}
      
     

演示样例：

const char S1[] = "Hello, world!";const char S2[] = "world";const int N1 = sizeof(S1) - 1;const int N2 = sizeof(S2) - 1;const char* p = search(S1, S1 + N1, S2, S2 + N2);printf("Found subsequence \"%s\" at character %d of sequence \"%s\".\n",	 S2, p - S1, S1);