日期：2017-7-11
思路：KMP，以前学的数据结构都忘光了，写的不是很好，有很多改进的地方
*/
#include <iostream> using namespace std; class StrStr{ public: /** * Returns a index to the first occurrence of target in source, * or -1 if target is not part of source. * @param source string to be scanned. * @param target string containing the sequence of characters to match. */ int strStr(const char *source, const char *target) { // write your code here //cout << source << endl; //cout << target << endl; int res = -1; if (source == NULL || target == NULL) return res; if (source[0] == '\0' && target[0] == '\0') { res = 0; return res; } else if (source[0] == '\0' || target[0] == '\0') { if (source[0] == 0) res = -1; if (target[0] == 0) res = 0; return res; } int i = 0; int j = 0; int targetCount = 0; while (target[j] != '\0') { targetCount++; j++; } //cout << targetCount << endl; j = 0; int index = 0; int sourceCount = 0; bool is = true; while (source[i] != '\0') { if (source[i] == target[j] && target[j] != '\0') { if (is) { index = i; is = false; } j++; i++; sourceCount++; } else { if (j == targetCount) { res = index; break; } is = true; j = 0; i = i - sourceCount + 1; sourceCount = 0; } } if (j == targetCount) res = index; return res; } };