1 #include<iostream> 2 #include<string> 3 #include<vector> 4 #include<map> 5 #include<text.hpp> 6 #include<ctime> 7 8 using namespace std; 9 clock_t begin, end; 10 11 template<typename C, typename I>struct Map { 12 Map() = default; 13 vector<C>vecC; 14 vector<I>vecI; 15 void insert(C c, I i) { 16 vecC.push_back(c); 17 vecI.push_back(i); 18 } 19 void traverse() 20 { 21 for (size_t i = 0; i < vecC.size(); ++i) { 22 cout << vecC[i] << " "<<vecI[i]<<ends; 23 } 24 } 25 auto find(I i) 26 { 27 return vecI.begin() + i; 28 } 29 30 }; 31 Map<char, int> create_next(const string& Pattern); 32 33 int kmp_index(const string& Text, const string& Pattern) { 34 clock_t begin = clock(); 35 auto mymap=create_next(Pattern); 36 int hadmatched = 0; 37 if (Text.size() < Pattern.size())return -1; 38 size_t Tofi = 0; size_t Pofj = 0; 39 while (Tofi < Text.size() && Pofj < Pattern.size()) 40 { 41 42 if (Text[Tofi] != Pattern[Pofj]&&!hadmatched) 43 Tofi++; 44 else if(Text[Tofi] == Pattern[Pofj]) 45 { 46 Tofi++; 47 Pofj++; 48 hadmatched++; 49 } 50 else if (Text[Tofi] != Pattern[Pofj] && hadmatched) 51 { 52 /*cout << "pofj"<<Pofj << endl; 53 cout << "had"<<hadmatched << endl;*/ 54 Pofj -= hadmatched - *mymap.find(hadmatched - 1); 55 hadmatched= Pofj; 56 } 57 58 59 } 60 clock_t end=clock(); 61 cout << static_cast<double>(end - begin)<<"毫秒"<< endl; 62 if (Pofj == Pattern.size()) 63 return Tofi-Pattern.size(); 64 else return -1; 65 } 66 Map<char,int> create_next(const string& Pattern){ 67 Map<char, int>m; 68 size_t size = Pattern.size(); 69 for (auto i : Pattern) 70 m.insert(i,0); 71 for (size_t i = 0; i < size; ++i) { 72 string begin, end = ""; 73 for (size_t j = 0; j < i; ++j) { 74 begin += Pattern[j]; 75 end =Pattern[i-j]+end; 76 if(begin==end) 77 { 78 *m.find(i)=begin.size(); 79 } 80 } 81 } 82 return m; 83 } 84 85 86 int bf_index(const string& Text, const string& Pattern) { 87 clock_t begin=clock(); 88 if (Text.size() < Pattern.size())return -1; 89 size_t Tofi = 0; size_t Pofj = 0; 90 while (Tofi < Text.size() && Pofj < Pattern.size()) 91 { 92 if (Text[Tofi] == Pattern[Pofj]) 93 { 94 Tofi++; 95 Pofj++; 96 } 97 else if (Text[Tofi] != Pattern[Pofj]) 98 { 99 Tofi = Tofi - Pofj + 1; 100 Pofj = 0; 101 } 102 } 103 clock_t end=clock(); 104 cout << static_cast<double>(end - begin)<<"毫秒" << endl; 105 if (Pofj == Pattern.size()) 106 return Tofi - Pattern.size(); 107 else return -1; 108 } 109 110 int bm_index(const string& Text, const string& Pattern) { 111 clock_t begin = clock(); 112 if (Text.size() < Pattern.size())return -1; 113 size_t Tofi = Pattern.size()-1; size_t Pofj = Tofi; 114 s:while (Tofi <= Text.size() && Pofj >0) { 115 /* cout << Tofi<< " " << Pofj << endl; 116 cout << Text[Tofi] << " " << Pattern[Pofj] << endl;*/ 117 if (Text[Tofi] == Pattern[Pofj]) { 118 Tofi--; 119 Pofj--; 120 } 121 else { 122 auto cp = Text[Tofi]; 123 size_t times = 0; 124 for (size_t i = Pofj; i > 0; --i) { 125 times++; 126 if (cp == Pattern[i]) 127 { 128 Tofi+=times-1; 129 goto s; 130 } 131 } 132 Tofi += Pattern.size(); 133 Pofj = Pattern.size()-1; 134 } 135 } 136 clock_t end = clock(); 137 cout << static_cast<double>(end - begin) << "毫秒" << endl; 138 if (Pofj == 0) 139 return Tofi; 140 else return -1; 141 } 142 143 inline void print(int i,const string &s2,const string & s){ 144 if (i == -1) { cout << "查找失败"; } 145 else { 146 cout << "字符串第" << i + 1 << "位" << endl; 147 for (size_t j = 0; j < s.size(); ++j) { 148 cout << s2[i + j]; 149 } 150 } 151 cout << "匹配字符串共" << s2.size() << "位" << endl; 152 } 153 154 int main() { 155 text(10000000).creat("random_1.txt"); 156 /*string s="EXAMPLE"; 157 string s2="HERE IS A SIMPLE EXAMPLQ EXAMPLE";*/ 158 string s,s2; 159 cin >> s; 160 ifstream iff("random_1.txt"); 161 iff >> s2; 162 163 cout << "bm算法" << endl; 164 int i = bm_index(s2, s); 165 print(i,s2,s); 166 cout << "kmp算法" << endl; 167 int j = kmp_index(s2, s); 168 print(j,s2,s); 169 cout << "bf算法" << endl; 170 int z = bf_index(s2, s); 171 print(z,s2,s); 172 173 174 175 }
更新，写错了 size_t 会把比较的-1变成正数找了半天bug
1 #include<iostream> 2 #include<string> 3 #include<vector> 4 #include<map> 5 #include<text.hpp> 6 #include<ctime> 7 8 using namespace std; 9 clock_t begin, end; 10 11 template<typename C, typename I>struct Map { 12 Map() = default; 13 vector<C>vecC; 14 vector<I>vecI; 15 void insert(C c, I i) { 16 vecC.push_back(c); 17 vecI.push_back(i); 18 } 19 void traverse() 20 { 21 for (size_t i = 0; i < vecC.size(); ++i) { 22 cout << vecC[i] << " " << vecI[i] << ends; 23 } 24 } 25 auto find(I i) 26 { 27 return vecI.begin() + i; 28 } 29 30 }; 31 Map<char, int> create_next(const string& Pattern); 32 33 int kmp_index(const string& Text, const string& Pattern) { 34 clock_t begin = clock(); 35 auto mymap = create_next(Pattern); 36 int hadmatched = 0; 37 if (Text.size() < Pattern.size())return -1; 38 size_t Tofi = 0; size_t Pofj = 0; 39 while (Tofi < Text.size() && Pofj < Pattern.size()) 40 { 41 42 if (Text[Tofi] != Pattern[Pofj] && !hadmatched) 43 Tofi++; 44 else if (Text[Tofi] == Pattern[Pofj]) 45 { 46 Tofi++; 47 Pofj++; 48 hadmatched++; 49 } 50 else if (Text[Tofi] != Pattern[Pofj] && hadmatched) 51 { 52 /*cout << "pofj"<<Pofj << endl; 53 cout << "had"<<hadmatched << endl;*/ 54 Pofj -= hadmatched - *mymap.find(hadmatched - 1); 55 hadmatched = Pofj; 56 } 57 58 59 } 60 clock_t end = clock(); 61 cout << static_cast<double>(end - begin) << "毫秒" << endl; 62 if (Pofj == Pattern.size()) 63 return Tofi - Pattern.size(); 64 else return -1; 65 } 66 Map<char, int> create_next(const string& Pattern) { 67 Map<char, int>m; 68 size_t size = Pattern.size(); 69 for (auto i : Pattern) 70 m.insert(i, 0); 71 for (size_t i = 0; i < size; ++i) { 72 string begin, end = ""; 73 for (size_t j = 0; j < i; ++j) { 74 begin += Pattern[j]; 75 end = Pattern[i - j] + end; 76 if (begin == end) 77 { 78 *m.find(i) = begin.size(); 79 } 80 } 81 } 82 return m; 83 } 84 85 86 int bf_index(const string& Text, const string& Pattern) { 87 clock_t begin = clock(); 88 if (Text.size() < Pattern.size())return -1; 89 size_t Tofi = 0; size_t Pofj = 0; 90 while (Tofi < Text.size() && Pofj < Pattern.size()) 91 { 92 if (Text[Tofi] == Pattern[Pofj]) 93 { 94 Tofi++; 95 Pofj++; 96 } 97 else if (Text[Tofi] != Pattern[Pofj]) 98 { 99 Tofi = Tofi - Pofj + 1; 100 Pofj = 0; 101 } 102 } 103 clock_t end = clock(); 104 cout << static_cast<double>(end - begin) << "毫秒" << endl; 105 if (Pofj == Pattern.size()) 106 return Tofi - Pattern.size(); 107 else return -1; 108 } 109 110 int bm_index(const string& Text, const string& Pattern) { 111 clock_t begin = clock(); 112 if (Text.size() < Pattern.size())return -1; 113 int Tofi = Pattern.size() - 1; int Pofj = Tofi; 114 s:while (Tofi <= static_cast<int>(Text.size()) && Pofj >-1) { 115 /*cout << Tofi<< " " << Pofj << endl; 116 cout << Text[Tofi] << " " << Pattern[Pofj] << endl;*/ 117 if (Text[Tofi] == Pattern[Pofj]) { 118 Tofi--; 119 Pofj--; 120 } 121 else { 122 auto cp = Text[Tofi]; 123 bool flag=false; 124 size_t times = 0; 125 for (int i = Pofj; i>=0; --i) { 126 times++; 127 if (cp == Pattern[i]) 128 { 129 flag = true; 130 Tofi += times - 1; 131 goto s; 132 } 133 } 134 //cout << "times" << times << endl; 135 Tofi += Pattern.size(); 136 Pofj = Pattern.size() - 1; 137 } 138 } 139 clock_t end = clock(); 140 cout << static_cast<double>(end - begin) << "毫秒" << endl; 141 if (Pofj == -1) 142 return ++Tofi; 143 else return -1; 144 } 145 146 inline void print(int i, const string& s2, const string& s) { 147 if (i == -1) { cout << "查找失败"; } 148 else { 149 cout << "字符串第" << i + 1 << "位" << endl; 150 151 for (size_t j = 0; j < s.size(); ++j) { 152 cout << s2[i + j]; 153 } 154 } 155 cout << "匹配字符串共" << s2.size() << "位" << endl; 156 } 157 158 int main() { 159 //text(10000000).creat("random_1.txt"); 160 /* string s=" alt"; 161 string s2="klt clt alt oel sihadhai.jsiajsiajdaduhudsa,,siajisaSAHDIA";*/ 162 string s, s2; 163 cin >> s; 164 ifstream iff("random_1.txt"); 165 iff >> s2; 166 167 cout << "bm算法" << endl; 168 int i = bm_index(s2, s); 169 print(i, s2, s); 170 cout << "kmp算法" << endl; 171 int j = kmp_index(s2, s); 172 print(j, s2, s); 173 cout << "bf算法" << endl; 174 int z = bf_index(s2, s); 175 print(z, s2, s); 176 177 178 179 }