# Produce different output - Wrong Answer based on KMP

• The algorithm is absolutely linear time complexity.

However, on case: {"b", "*?*?"}

My local output: false

Submitted output: true

Expected output: false

``````class Solution {
public:
int *next;

void getNext(const char *p, int len) {
int i=0, j=-1;
next[0]=-1;
while (i<len) {
if (j==-1 || p[i]=='?' || p[j]=='?' || p[i]==p[j])
next[++i]=++j;
else
j=next[j];
}
}

bool isMatch(const char *s, const char *p) {
next=new int[strlen(p)+5];
while (*s && *p) {
if (*p=='*')
break;
if (*p=='?' || *s==*p)
p++, s++;
else
return false;
}
const char *q;
int w,i,j;
while (*p) {
while (*p=='*')
p++;
if (!*p)
return true;
for (q=p+1;*q && *q!='*'; q++);
int len=q-p;
getNext(p, len);
i=j=0;
bool found=false;
while (*s) {
if (j==-1 || p[j]=='?' || p[j]==*s) {
s++, j++;
if (j>=len) {
found=true;
break;
}
} else
j=next[j];
}
if (found)
s+=len, p=q;
else
return false;
}
return !*s;
}
};``````

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