1 KMP

class Solution {
public:
    char *strStr(char *haystack,char *needle) {
        int n=strlen(needle);
        if(n==0)  return haystack;
         //kmp
        vector<int> nxt(n+1);///@error: nxt should be sized n+1,not n. to contain the nxt[n]
        nxt[0]=-1;nxt[1]=0;
        for(int i=0;i<n;i++){
            int j=nxt[i];
            while(j>=0&&needle[i]!=needle[j]) j=nxt[j]; //i matched j
            nxt[i+1]=j+1;/////@@@@@@@error: nxt[i+1]=j+1; mistake as needle[i+1]=j+1;  an Array_Variable_Fault !!!!
        }
        int j=0;
        for(int i=0;haystack[i]!=0;i++,j++){
            while(j>=0&&haystack[i]!=needle[j]) j=nxt[j];//i matched j
            if(j==n-1) return haystack+i-j; //matche needle
        }
        return NULL;
    }
};

正则匹配不同于一般匹配。回溯取决于*号出现的位置。

采用贪心法：p中'*'尽量匹配s中最少的字符，从上到下执行规则：

1.1如果p到达0,s未到达0: 则回溯或匹配失败

1.2 如果p到达0,s到达0: 则成功

2.1如果p为'*':设置回溯点，p前进

3.1 如果p不为0或'*',而s到达0: 则匹配失败

3.2 如果p不为0或'*',s不为0: p=s或p='?'则s、p前进；否则回溯或匹配失败。

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
 
The matching should cover the entire input string (not partial).
 
The function prototype should be:
bool isMatch(const char *s,const char *p)
 
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa","*") → true
isMatch("aa","a*") → true
isMatch("ab","?*") → true
isMatch("aab","c*a*b") → false

class Solution {
public:
    bool isMatch(const char *s,const char *p) {
       const char *pre_s,*pre_p;bool star=false;///@@error:pre_s pre_p must be const,or invalid conversion from 'const char*' to 'char*' [-fpermissive]
       while(true){
           if(*p==0){
             if(*s==0) return true;  //*p=0 and *p matches *s
             if(!star) return false; //*p=0!=*s
             s=++pre_s;p=pre_p;
           }
           else if(*p!='*'){
                if(*p==*s||*p=='?'&&*s!=0) s++,p++;//*p!=0 and *p matches *s (then *s!=0)
                else {
                    if(!star||*s==0) return false;///@warning:when *s=0,say s reaches the end,p will not match it even if Star=true
                    s=++pre_s;p=pre_p;
                }
           }else{
                star=true;
                pre_s=s,pre_p=p+1;
                p=pre_p;
           }
       }
    }
};

或者

class Solution {
public:
 bool isMatch(const char *s,const char *p) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    const char *pre_s = s,*pre_p = p;//保存上一次开始匹配的位置
    bool has_star = false;
 
    while (*s) {
      if (*s != *p) {
        if (*p == '?') s++,p++;
        else if (*p == '*') {
          has_star = true;
          while (*p == '*') p++;
          if (*p == '\0') return true;
          pre_s = s,pre_p = p;//置上一个开始比较的位置
        } else if (has_star) {
          pre_s++;
          s = pre_s,p = pre_p;//恢复到上一次比较的下一个位置
        } else return false;   //*s!=0 and *s!=*p and *p!='?' and !hasStar
      } else s++,p++;
    }
    //s has reach the end,so p's remainning part must match ''.
    while (*p == '*') p++;
    return *p == '\0';
  }
};

或者：

class Solution {
public:
    bool isMatch(const char *s,const char *p) {
        bool tag = false; 
        const char * pre_s,*pre_p;
        while(*s){
            if(*s==*p || *p=='?') s++,p++;
            else if(*p=='*'){
                tag = true;
                pre_s = s,pre_p = ++p;
            }
            else{
                if(tag){
                s = ++ls,p = pre_p;
                }
                else return false;
            }
        }
        while(*p == '*') p++;
        return *p==0;
    }
};

'.' Matches any single character.
'*' Matches zero or more of the preceding element.
 
The matching should cover the entire input string (not partial).
 
The function prototype should be:
bool isMatch(const char *s,"a*") → true
isMatch("aa",".*") → true
isMatch("ab",".*") → true
isMatch("aab","c*a*b") → true

class Solution {
public:
  inline bool match(char a,char b){
    //assert(a!='*');
    if(a=='.') return true;
    return a==b;
  }
  bool isMatch(const char *s,const char *p) {
    int n=strlen(p),m=strlen(s);
    vector<vector<bool> > a(n+1,vector<bool>(m+1,false));
 
    a[0][0]=true;
    /*
    for(int i=2;i<=n;i+=2){
      if(p[i-1]!='*') break;
      a[i][0]=true;
    }
    for(int j=1;j<=m;j++)
      a[0][j]=false;
    */
 
    for(int i=1;i<=n;i++){
      if(i<n&&p[i]=='*') continue;//i++,go to '*'
      if(p[i-1]=='*'){
        assert(i>1&&p[i-2]!='*');
        char c=p[i-2];
        bool lc=false;
        for(int j=0;j<=m;j++){//1-dim dp
          if(j>0&&lc) lc=match(c,s[j-1]);///@error:s[j-1] fault as a[j-1]///@error:if(j>0&&lc&&match(c,s[j-1])) lc=true; here,when lc=true,lc should be false if match(c,s[j-1])=false
          if(a[i-2][j]) lc=true;
          a[i][j]=lc;
        }      
      }
      else
         for(int j=1;j<=m;j++){
            if((p[i-1]==s[j-1]||p[i-1]=='.')&& a[i-1][j-1]) a[i][j]=true;
      }
    }
    return a[n][m];
  }
};