作者: kingoal
给定一个输入的字符串t(text)，长度为n(n=strlen(t))，给出匹配模式p(pattern)，长度为m(m=strlen(p)).
在Introduction to algorithm书(CLRS)中，字符串算法主要是讨论了4种，分别对应的是：
朴素(Naive) ----------O(m*(n-m+1))
Rabin-Karp-----------O(m*(n-m+1))
有限自动机-----------O(n)
Knuth-Morris-Pratt------------------O(n)
下面分4部分具体介绍该4种字符串匹配算法。
Naive算法非常简单，就是将t的字节从0到n-m+1来一一匹配p的m个字符，若所有的m字符都匹配成功，则输出匹配成功，输出当前的index值。
下面给出Naive的实现代码：
1 #include <iostream>
2 #include <string>
3
4 using namespace std;
5
6 int main(int argc,char* argv[])
7 {
8 char *t=NULL,*p=NULL;
9 string text,pattern;
10
11 while(1)
12 {
13 int index = 0;
14
15 cin>>text>>pattern;
16 int n = text.length();
17 int m = pattern.length();
18
19 //t= new char[n+1];
20 //p= new char[m+1];
21 t= new char[n];
22 p= new char[m];
23
24 //strcpy(t,text.c_str());
25 //strcpy(p,pattern.c_str());
26 memcpy(t,text.data(),n);
27 memcpy(p,pattern.data(),m);
28
29 for(int i=0;i<n-m+1;i++)
30 {
31 bool match=true;
32
33 for(int j=0;j<m;j++)
34 {
35 if(t[i+j]!=p[j])
36 match=false;
37 }
38 if(match)
39 cout<<index<<endl;
40
41 index++;
42 }
43
44 delete[] t;
45 delete[] p;
46 }
47
48 system("pause");
49 return 0;
50 }
51