【字符串匹配】KMP（implement strStr()), 正则匹配(Wildcard Matching)，2-dim 动规（regular expression)
1 KMP
Implement strStr()
Total Accepted:15450
Total Submissions:71217
My Submissions
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack,ornullif needle is not part of haystack.
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前进；否则回溯或匹配失败。
Wildcard Matching
Total Accepted:10189
Total Submissions:75093
My Submissions
@H_
403_112@
Implement wildcard pattern matching with support for'?'and'*'.
@H_
404_123@'?' 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;
}
};
@H_
403_112@
Regular Expression Matching
Total Accepted:13590
Total Submissions:68280
My Submissions
Implement regular expression matching with support for'.'and'*'.
'.' 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
