Thank you for sharing your code. I was solving this problem via KMP algorithm too with similar idea. But it seems no way for me to come up a O(m+n) solution.

to generate KMP table vector<int> table(n, 0); , it takes O(n) space.

considering how many times the following code could be excuted (worst case O(m))

if(*lastP != '\0'){
lastS++;
s = lastS;
p = lastP;
}

since help(s, p, n) is O(n), the worst case time complexity of the code is still O(mn).

for example: aa...(20000 a's)...aabaa...(1000 a's) and *aa?aa?...(5000 aa?)...aab*

it will run lastS++ 5000 times, and for each time, it will go through whole *aa?aa?...(5000 aa?)...aab* to find the last b not matched. thus it will take approximately 5000*15000 to find the match.

The other posted KMP solution seems have the same problem.

I am not sure if there is a O(m+n) algorithm could solve cases like this.