作者: kingoal
給定一個(gè)輸入的字符串t(text)，長(zhǎng)度為n(n=strlen(t))，給出匹配模式p(pattern)，長(zhǎng)度為m(m=strlen(p)).
在Introduction to algorithm書(shū)(CLRS)中，字符串算法主要是討論了4種，分別對(duì)應(yīng)的是：
樸素(Naive) ----------O(m*(n-m+1))
Rabin-Karp-----------O(m*(n-m+1))
有限自動(dòng)機(jī)-----------O(n)
Knuth-Morris-Pratt------------------O(n)
下面分4部分具體介紹該4種字符串匹配算法。
Naive算法非常簡(jiǎn)單，就是將t的字節(jié)從0到n-m+1來(lái)一一匹配p的m個(gè)字符，若所有的m字符都匹配成功，則輸出匹配成功，輸出當(dāng)前的index值。
下面給出Naive的實(shí)現(xiàn)代碼：
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