# A 20ms solution based on the kmp search

• ``````class Solution {
public: bool isMatch(string s, string p){
const char* text= s.c_str();
int tlen= s.size();
const char* pat = p.c_str();
int max_plen=p.size();

// check if the left most subtring not containing * of p matches the corresponding subtring of s
for (; tlen > 0 && (text[0] == pat[0] || pat[0] == '?') && pat[0] != '*'; text++, pat++, max_plen--, tlen--);
if (max_plen > 0 && pat[0] != '*') return false;

// check if the right most subtring not containing * of p matches the corresponding subtring of s
for (; tlen > 0 && max_plen > 0 && (text[tlen - 1] == pat[max_plen - 1] || pat[max_plen - 1] == '?'); tlen--, max_plen--);
if (max_plen == 0) { return tlen == 0; }
else if (max_plen > 0 && pat[max_plen - 1] != '*') return false;

//the substring of p in the form of *p1*p2*...pn* ,  where p1...,pn is string not containg *
//sequently checking if every pi is in s
int plen;
while (true) {
while (*pat == '*') {
pat++;
max_plen--;
}
plen = 0;
for (; plen< max_plen && pat[plen] != '*'; plen++);
int pos = kmp(text, tlen, pat, plen);
if (pos < 0) return false;
text += pos + plen;
tlen -= pos + plen;
pat += plen;
max_plen -= plen;
if (max_plen == 0) return true;

}
}

// if text contains pat , return the postion of the first match, else return -1
int kmp(const char* text, int tlen, const char* pat, int plen) {
if (plen == 0) return 0;
vector<int> nexts(plen + 1, 0);
for (int i = 2; i <= plen; i++) {
for (int j = i; j > 0;) {
if (pat[j - 1] == '?' || pat[i - 1] == pat[nexts[j - 1]]) {
nexts[i] = nexts[j - 1] + 1;
break;
}
else if (pat[nexts[j - 1]] == '?') {
int m = j - 1, n = nexts[j - 1], temp;
do {
temp = m;
m = n;
n = 2 * n - temp;
} while (pat[n] == '?'&& n > 0);
if (n>0 && pat[n] != '?'&& pat[n] != pat[j - 1])
j = nexts[j - 1];
else {
nexts[i] = nexts[j - 1] + 1;
break;
}
}
else j = nexts[j - 1];
}
}
int i = 0, j = 0;
while (i<tlen) {
for (; i<tlen && j< plen && (text[i] == pat[j] || pat[j] == '?'); i++, j++);
if (j == plen) return i - j;
for (; j > 0 && text[i] != pat[j] && pat[j] != '?'; j = nexts[j]);
if (text[i] != pat[j] && pat[j] != '?') {
i++;
j = 0;
}
}
return -1;
}
``````

};

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