1 #include<iostream>  2 #include<string>  3 using namespace std;  4   5 /* 朴素的模式匹配法 */  6 int Index(string s, string t, int pos)  7 {  8     int i = pos;  9     int j = 0; 10     int len_1 = s.size(); 11     int len_2 = t.size(); 12     while(i<len_1 && j<len_2) 13     { 14         if(s[i] == t[j]) 15         { 16             i++; 17             j++; 18         } 19         else 20         { 21             i = i-j+1; 22             j = 0; 23         } 24     } 25     if(j>=len_2) 26         return i-len_2; 27     else 28         return 0; 29 } 30  31 /* 通过计算返回子串T的next数组。 */ 32 void get_next(string T, int *next) 33 { 34     int len = T.size(); 35     int i = 0; 36     int j = -1; 37     next[0] = -1; 38     while(i<len-1) 39     { 40         if(j==-1 || T[i]==T[j]) 41         { 42             ++i; 43             ++j; 44             next[i] = j; 45         } 46         else 47             j = next[j]; 48     } 49 } 50 /* KMP算法 */ 51 int Index_KMP1(string s, string t, int pos) 52 { 53     int i = pos; 54     int j = 0; 55     int size1 = s.size(); 56     int size2 = t.size(); 57     //int *next = new int[size1]; 58     int next[255] = {0}; 59     get_next(t,next); 60     while(i<size1 && j<size2) 61     { 62         if(j==-1 || s[i]==t[j]) 63         { 64             i++; 65             j++; 66         } 67         else 68         { 69             j = next[j]; 70         } 71     } 72     if(j>=size2) 73     { 74         return i-size2; 75     } 76     else 77         return 0; 78 } 79  80 /* 求模式串T的next函数修正值并存入数组nextval */ 81 void get_nextval(string T, int *nextval) 82 { 83     int len = T.size(); 84     int i = 0; 85     int j = -1; 86     nextval[0] = -1; 87     while(i<len-1) 88     { 89         if(j==-1 || T[i]==T[j]) 90         { 91             ++i; 92             ++j; 93             if(T[i] != T[j]) 94                 nextval[i] = j; 95             else 96                 nextval[i] = nextval[j]; 97         } 98         else 99             j = nextval[j];100     }101 }102 103 /* 改进的KMP算法 */104 int Index_KMP2(string s, string t, int pos)105 {106     int i = pos;107     int j = 0;108     int size1 = s.size();109     int size2 = t.size();110     //int *next = new int[size1];111     int nextval[255] = {0};112     get_nextval(t,nextval);113     while(i<size1 && j<size2)114     {115         if(j==-1 || s[i]==t[j])116         {117             i++;118             j++;119         }120         else121         {122             j = nextval[j];123         }124     }125     if(j>=size2)126     {127         return i-size2;128     }129     else130         return 0;131 }132 133 int main()134 {135     //char str_2[6] = "abcde";136     //string str1 = "abcdex";137     //string str2 = "abcabx";138     //string str3 = "ababaaaba";139     string str4 = "aaaaaaaab";140 141     string s1 = "abaabcabx";142     string t1 = "abcabx"; 143 144     string s2 = "abcba";145     string t2 = "cba"; 146 147     cout<<Index(s2,t2,0)<<endl;148     cout<<Index_KMP1(s2,t2,0)<<endl;149     cout<<Index_KMP2(s2,t2,0)<<endl;150 151     int arr1[255] = {0};152     int arr2[255] = {0};153     get_next(str4, arr1);154     get_nextval(str4, arr2);155     for(int i=0; i<str4.size(); i++)156         cout<<arr1[i];157     for(int i=0; i<str4.size(); i++)158         cout<<arr2[i];159 160     /*string aa = "12345";161     cout<<aa.size()<<endl;162     for(int i=0;i<2;i++)163         aa[i] = ‘a‘;164     cout<<aa.size()<<endl;165     cout<<aa<<endl;*/166 167     return 0;168 }