数据结构清华大学出版社，4.3节
基本思想：主串S， 模式串T， 求模式串在主串中某一个pos位置开始查找，返回其出现的位置。用i 和 j分别指示指向当前主串S和模式串T元素的下标，从0开始。
首先将主串S的pos位置元素和模式串0位置元素开始比较，如果相等则 i 和 j 都加1，否则i回溯，j回到0。i回溯到的值为i - j + 1，课本上是i - j + 2，因为课本用的下标是从1开始，而我们这里是从0开始。 直到i 或 j 超过了主串S 或 模式串T的最后一个元素位置。
代码如下：
1 // StringMatch.cpp : 定义控制台应用程序的入口点。
2 //
3
4 #include "stdafx.h"
5 #include <iostream>
6 using namespace std;
7
8 //strMain为主串
9 //strMatch为模式串
10 //返回模式串在pos位置开始查找的出现位置
11 //pos最小为0，最大为主串长度 - 模式串长度
12 //eg. strMain == "hello"
13 //strMatch == "ll", 则pos最大为5 - 2 == 3
14 int StringMatch(const TCHAR* strMain, const TCHAR* strMatch, size_t pos)
15 {
16 size_t nMain = _tcslen(strMain);
17 size_t nMatch = _tcslen(strMatch);
18
19 if (NULL == strMain || NULL == strMatch //输入为空
20 || pos > (nMain - 1) //起始位置超过主串最后一个位置
21 || pos > (nMain - nMatch) //起始位置超过一个合理的位置
22 || nMatch > nMain //模式串长度大于主串
23 )
24 {
25 return -1;
26 }
27
28 size_t i = pos; //主串的比较的起始位置
29 size_t j = 0; //模式串比较的起始位置
30
31 int index = -1; //返回的位置;
32
33 while ( i < nMain && j < nMatch )
34 {
35 if (strMain[i] == strMatch[j])
36 {
37 ++i; ++j;
38 }
39 //回溯
40 else
41 {
42 j = 0;
43 i = i - j + 1;
44 }
45 }
46
47 if (j >= nMatch)
48 {
49 index = i - nMatch;
50 }
51 else
52 {
53 index = -1;
54 }
55
56 return index;
57
58 }
59
60
61 int _tmain(int argc, _TCHAR* argv[])
62 {
63 const TCHAR* lpMain = _T("helloworld");
64 const TCHAR* lpMatch = _T("oworl");
65 size_t pos = 3;
66
67
68 wcout<<"模式串"<<lpMatch<<"在主串"<<lpMain<<"中"<<pos<<"位置开始查找，出现的位置是"<<StringMatch(lpMain, lpMatch, pos)<<endl;
69
70 return 0;
71 }
运行结果如下：
