``` /* strStr */ #include #include #include using namespace std; vector getNext(string pattern) { int length = pattern.length(); vector res(length, 0); res[0] = 0; for(int i = 1; i < length; i++) { int k = res[i-1]; while(pattern[i] != pattern[k] && k != 0) { k = res[k-1]; } if(pattern[i] == pattern[k]) { res[i] = k + 1; } else { res[i] = 0; } } return res; } int KMP(string srcStr, string pattern) { int length1 = srcStr.length(); int length2 = pattern.length(); vector next = getNext(pattern); int j = 0; for(int i = 0; i < length1; i++) { while(srcStr[i] != pattern[j] && j != 0) { j = next[j-1]; } if(srcStr[i] == pattern[j]) { j++; } if(j == length2) { return i - length2 + 1; } } return -1; } int main() { string s = "acgtacgacgtacgacgtacgtg"; string pattern = "acgacgt"; cout << KMP(s, pattern) << endl; return 0; } /* Two String Are Anagrams */ #include #include #include using namespace std; bool anagrams(string s, string t) { int length1 = s.length(); int length2 = t.length(); if(length1 != length2) { return false; } vector charset(256, 0); for(int i = 0; i < length1; i++) { charset[s[i]]++; } for(int i = 0; i < length2; i++) { charset[t[i]]--; } for(int i = 0; i < 256; i++) { if(charset[i] != 0) { return false; } } return true; } int main() { string s = "abcd"; string t = "bcda"; cout << anagrams(s, t) << endl; } /* * Compare Strings * anagrams的变形题 * */ #include #include #include using namespace std; bool compareStrings(string A, string B) { int length1 = A.length(); int length2 = B.length(); map charset; map::iterator it; for(int i = 0; i < length1; i++) { it = charset.find(A[i]); if(it != charset.end()) { charset[A[i]]++; } else { charset[A[i]] = 1; } } for(int i = 0; i < length2; i++) { it = charset.find(B[i]); if(it != charset.end()) { if(charset[B[i]] <= 0) { return false; } else { charset[B[i]]--; } } else { return false; } } return true; } int main() { string A = "AABCD"; string B = "AABC"; cout << compareStrings(A, B) << endl; } /* * anagrams * */ #include #include #include using namespace std; class Solution { public: vector findAnagrams(string s, string p) { int length1 = s.length(); int length2 = p.length(); vector res, v1(256, 0), v2(256, 0); if(s.empty()) return res; for(int i = 0; i < length2; i++) { ++v1[s[i]]; ++v2[p[i]]; } if(v1 == v2) res.push_back(0); for(int i = length2; i < length1; i++) { ++v1[s[i]]; --v1[s[i - length2]]; if(v1 == v2) res.push_back(i - p.size() + 1); } return res; } }; int main() { string s = "cbaebabacd"; string p = "abc"; Solution *sol = new Solution(); vector res = sol->findAnagrams(s, p); for(int i = 0; i < res.size(); i++) { cout << res[i] << endl; } } /* 最长公共子串 */ #include #include #include using namespace std; class Solution { public: /** * @param A: A string * @param B: A string * @return: the length of the longest common substring. */ int longestCommonSubstring(string &A, string &B) { int length1 = A.length(); int length2 = B.length(); int max = 0; if(length1 == 0 || length2 == 0) { return 0; } vector > table; for(int i = 0; i < length1; i++) { table.push_back(vector(length2, 0)); } //初始化 for(int i = 0; i < length1; i++) { if(A[i] == B[0]) { table[i][0] = 1; max = max > table[i][0] ? max : table[i][0]; } } for(int i = 0; i < length2; i++) { if(A[0] == B[i]) { table[0][i] = 1; max = max > table[0][i] ? max : table[0][i]; } } for(int i = 1; i < length1; i++) { for(int j = 1; j < length2; j++) { if(A[i] == B[j]) { table[i][j] = 1 + table[i-1][j-1]; max = max > table[i][j] ? max : table[i][j]; } else { table[i][j] = 0; } } } return max; } }; int main(int argc, char const *argv[]) { string s1 = "abcd"; string s2 = "cbce"; Solution* s = new Solution(); cout << s->longestCommonSubstring(s1, s2) << endl; int temp; cin >> temp; return 0; } /* * 按给定的偏移量进行旋转字符串 * */ #include #include using namespace std; class Solution { public: string rotateString(string A, int offset) { int length = A.length(); if(length == 0) return A; offset = offset % length; reverse(A, 0, length - offset - 1); reverse(A, length - offset, length - 1); reverse(A, 0, length - 1); return A; } private: void reverse(string& str, int begin, int end) { int i= begin, j = end; while(i < j) { char temp = str[i]; str[i] = str[j]; str[j] = temp; i++; j--; } } }; int main() { Solution* s = new Solution(); cout << s->rotateString("abcdefg", 3) << endl; } ```

“经典算法解题实战”实验报告