??#include

#include

#include

//1、'?'很好處理，只要在原有的定位函數(shù)中加一點點就行：

int index(char *s,char *t,int pos)

int i=pos,j=0,lens=strlen(s),lent=strlen(t);

while(i {

if(s[i]==t[j]||t[j]=='?')

i;

j;

else

i=i-j 1;

j=0;

if(j==lent)return i-lent;

else return -1;

/*2、'*'的處理有些麻煩，很自然的想法是'*'把整個T串分成若干不含'*'的子串，

拿這些子串依次匹配S串。

按這樣的方法可以把S串分成兩類：

A、T=T1*T2*。。。Tn*，其中Ti為不含'*'的子串，且不為空（T1可為空）。

B、T=T1*T2*。。。Tn

二者的差別只在于尾部是否有'*'。

拿T匹配S，

首先 T1匹配S頭部，index(s,t1,0)==0

然后 用循環(huán)完成后面的匹配，從前一次匹配后的末尾位置開始向后匹配，

如果匹配成功再把末尾位置記錄下來。

??這里只用了最左匹配，為什么就足夠了呢？

比如實際中的情況T1串可能在S串不止出現(xiàn)一次，為什么只考慮最左一個呢？

因為整個匹配過程是從左向右，最左匹配可以保證余下的S子中最長，更有利于后面T子串的匹配成功，

試想如果T1最左匹配不成功，靠右一些有可能成功嗎？

例：T="*is*a*" S="this is a program"

T 子串"is"在S中有出現(xiàn)兩個位置，匹配的時候只需要考慮最左邊那個"is"就行了，

因為最左邊的"is"匹配成功后，余下的S子串是" is a program"，余下的T子串是"*a"，

最左匹配可使余下的S子串最長，匹配的可能最大，最容易匹配的情況已經(jīng)驗證了，

就不用再做無用功了。

int match(char *s,char *t)

int i=0,j=0,lens=strlen(s),lent=strlen(t);

char buf[128];

int bufp=0;

while(j {

buf[bufp]=t[j];

bufp; j;

buf[bufp]='