KMP, C++ 100%

• use kmp algorithm to find match in strings. An array to represent if one position belongs to a match.

``````class Solution {
private:
vector<int> calc_next(const string & pat) {
const int len = pat.size();
vector<int> next(len, -1);
for(int i = 1; i < len; ++i) {
for(int j = next[i-1];; j=next[j]) {
if(pat[i] == pat[j+1]) {
next[i] = j+1;
break;
}else if(-1 == j){
next[i] = -1;
break;
}
}
}

return next;
}
vector<pair<int, int>> kmp(const string &str, const string & pat, const vector<int> & next) {
int s = -1;
int p = -1;
const int str_len = str.size();
const int pat_len = pat.size();
vector<pair<int, int>> match_rg;
if(pat_len > 1) {
while(s < str_len) {
if(p == -1){
p = 0;
++s;
while(s < str_len && str[s] != pat[p]) {
++s;
}
}

if(s == str_len) {
break;
}

if(str[s+1] == pat[p+1]) {
++s;
++p;
}else {
p = next[p];
}

if(p == pat_len - 1) {
match_rg.push_back({s-pat_len+1, s});
p = next[p];
}
}
}else {
int s = 0;
while(s < str_len) {
if(str[s] == pat[0]) {
match_rg.push_back({s,s});
}
++s;
}
}

return match_rg;
}
public:
string addBoldTag(string s, vector<string>& dict) {
vector<bool> matched(s.size(), false);
for(const string & pat:dict) {
vector<int> next = calc_next(pat);
vector<pair<int, int>> match_rg= kmp(s, pat, next);
for(pair<int, int> rg:match_rg) {
for(int i = rg.first; i <= rg.second; ++i) {
matched[i] = true;
}
}
}

string res;
const int len = s.size();
for(int i = 0; i < len; ++i) {
if(matched[i] && (i==0 ||!matched[i-1])) {
res += "<b>";
}
res.push_back(s[i]);
if(matched[i] && (i== len -1 || !matched[i+1])) {
res += "</b>";
}
}
return res;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.