strStr II
Given a target string, and a searching space with a list of strings, find out whether the searching space contains the target string or not.
For example:
target = "is Fri"
search_spce = {"Today", " is", " Friday."}
return true;
implement function:bool contains(string target, list<string> search_space);
不要问我怎么知道这道题的！
Solution
暴力搜索的方法，每次从search space里面取出来一个跟target等长的substring去比较， 若相等则返回true，若到search space的end了（取不出来那么长的substring了）还没找到，则返回false。
这个暴力搜索不太容易通过一个字符一个字符的比较来做到，因为比较难在search sapce里面回溯。（strStr里面的i=i-j+1).
//O(mn) run time, m is the len of target, n is the total length of string in the searching space
//O(m) space
bool GetString(list<string>::iterator it, int pos, list<string>::iterator it_end, string &found_string, int len) {
while (found_string.length() < len) {
if (it == it_end) {
return false;
}
if (pos == (*it).length()) {
pos = 0;
it++;
}
found_string.append(1, (*it)[pos++]);
}
return true;
}
bool contains(string target, list<string> search_space) {
for (list<string>::iterator it = search_space.begin(); it != search_space.end(); it++) {
string search_string = *it;
for (int i = 0; i < search_string.length(); i++) {
//get a substring from search_space with length the same as target,
//then compare.
string substr_in_space;
bool can_get = GetString(it, i, search_space.end(), substr_in_space, target.length());
cout << substr_in_space << " " << substr_in_space.length()<<endl;
if (can_get == false) {
return false;
}
if (substr_in_space == target) {
return true;
}
}
}
return false;
}
Solution 2 KMP algorithm
既然上面也说了，search space不好回溯，因为不是一个string，那刚刚好KMP算法呢不需要移动source string，只是根据next查询表移动target。
如果会strStr的KMP algorithm的话，那这个题一点问题都没有。
bool GetChar(list<string>::iterator &it, int &pos, list<string>::iterator it_end, char &found_char) {
if (it == it_end) {
return false;
}
if (pos == (*it).length()) {
pos = 0;
it++;
}
found_char = (*it)[pos];
return true;
}
vector<int> GetNext(string target) {
int n = target.length();
vector<int> next(n, -1);
int i = 0;
int j = -1;
while (i < n - 1) {
if (j == -1 || target[i] == target[j]) { //then next[i+1] = j+1; one more common char between prefix and subfix
i++;
j++;
next[i] = j;
}
else {// not plus one anymore, check from next[j] to find a shorter common string between prefix and subfix
j = next[j];
}
}
return next;
}
bool contains(string target, list<string> search_space) {
if (search_space.empty()) return false;
if (target.length() == 0) return false;
vector<int> next = GetNext(target);
list<string>::iterator it = search_space.begin();
char search_c;
int i = 0;
int j = 0;
while (GetChar(it, i, search_space.end(), search_c)) {
if (j == -1 || search_c == target[j]) {
i++;
j++;
}
else {
j = next[j];
}
if (j == target.length()) return true;
}
return false;
}