C++ O(N+M) solution using KMP
class Solution {\n    public:\n        void GetLut(const char *p, int posp, int len, vector<int> *lut) {\n            (*lut)[0] = -1;\n            int pos = -1;
    class Solution {\n    public:\n        void GetLut(const char *p, int posp, int len, vector<int> *lut) {\n            (*lut)[0] = -1;\n            int pos = -1;\n            for (int i = 1; i < len; ++i) {\n                while (pos > -1 && p[posp+pos+1] != p[posp + i] && p[posp+pos+1] != '?' && p[posp+i] != '?')\n                    pos = (*lut)[pos];\n                if (p[posp+pos+1] == p[posp+i] || p[posp+pos+1] == '?' || p[posp+i] == '?') {\n                    (*lut)[i] = ++pos;\n                } else {\n                    (*lut)[i] = -1;\n                }\n            }\n        }\n        int MyStrStr(const char *s, int poss, int lens, const char *p, int posp, int len) {\n            if (lens - poss < len - posp) return -1;\n            vector<int> lut(len);\n            GetLut(p, posp, len, &lut);\n            int pos = -1;\n            for (int i = 0; i < lens - poss; ++i) {\n                while (pos > -1 && p[posp+pos+1] != s[poss + i] && p[posp+pos+1] != '?')\n                    pos = lut[pos];\n                if (p[posp+pos+1] == s[poss+i] || p[posp+pos+1] == '?') {\n                    ++pos;\n                    if (pos == len - 1) {\n                        return poss + i - len + 1;    \n                    }\n                }\n            }\n            return -1;\n        }\n        bool isMatch(const char *s, const char *p) {\n            int lens = 0;\n            while (s[lens] != '\\0') ++lens;\n            int lenp = 0;\n            while (p[lenp] != '\\0') ++lenp;\n            if (lens == 0 && lenp == 0) return true;\n            if (lenp == 0) return false;\n            vector<int> start;\n            vector<int> len;\n            int pos = 0;\n            for (int i = 0; i < lenp; ++i) {\n                if (p[i] != '*') {\n                    if (i == 0 || p[i-1] == '*') {\n                        pos = i;\n                    }\n                    if (i == lenp-1 || p[i+1] == '*') {\n                        start.push_back(pos);\n                        len.push_back(i - pos + 1);\n                    }\n                }\n            }\n            if (start.empty()) return true;\n            if (lens == 0 && !start.empty()) return false;\n            int poss = 0;\n            for (int i = 0; i < start.size(); ++i) {\n                int matchedpos = MyStrStr(s, poss, lens, p, start[i], len[i]);\n                if (matchedpos == -1) return false;\n                if (i ==  0 && p[0] != '*' && matchedpos > 0) return false;\n                poss = matchedpos + len[i];\n            }\n            if (start.size() == 1 && p[lenp-1] != '*' && p[0] != '*') {\n                if (lenp != lens) return false;\n                return 0 == MyStrStr(s, 0, lens, p, 0, lenp);\n            }\n            if (p[lenp-1] != '*') {\n                int matchedpos = MyStrStr(s, lens - len[len.size()-1], lens, p, start[start.size()-1], len[len.size()-1]);\n                if (matchedpos == -1) return false;\n            }\n            return true;\n        }\n    };\n\nstring p can be divided into several substring by '\\*'. Match the first substring of p from starting point of string s, then second substring after the matchpoint of the first, and so on. If match is not found, return false. If the first element of p is not '*', the first match must be 0. If the last element of p is not '*', the last match must be at end of s. \n\ntime complexity is O(n + m) where n is length of s and m is length of p.\n\nWe are using a slightly change of KMP (for '?') to do string matching. For each substring of p, let's say we found a match in s, so the time for this search is O(matchedpos + len(substr of p)). For next substring of p, we do a KMP from the mathcedpos + len(prev substr of p)) in s. If we could match all substrings of p in s, the time will be O(len(s) + len(p)). We did some modifications at the end but it didnot change the time complexity.
[]