1 /*  2 不使用c，c++库，？表示任意一个，*表示>=0任意，匹配规则要求匹配最大的字符子串，例如a*d ，匹配abbdd而非abbd,即最大匹配字符串  3 input ：abcadefg  4 reule : a?c  5 ouput : abc  6   7 input : newsadfanewfdsdsf  8 rule　：new  9 output: new new（最后一个不带空格，中间用空格分隔） 10  11 input : breakfastfood 12 rule  : f*d 13 output: fastfood 14  15 input : aaa 16 rule  :aa 17 outpur: aa 18  19 input : asdfgsdf 20 rule  :* 21 output :asdfgsdf 22 方法有两种，一种采用递归的方法，最大匹配函数，然后用调用给匹配算法，该函数都返回匹配个数，不匹配返回-1，以input的第一个开始算起，不匹配直接 23 -1，然后顺序遍历方法。 24 方法二：采用dp解决，dp问题dp[i][j]表示字符串1和字符串2分别以i和j结尾匹配最大长度 25 */ 26  27 #include 
     
       28 #include 
      
        29 using namespace std; 30  31 int strleng(const char * A) 32 { 33     if(A==NULL) 34         return 0; 35     const char * p=A; 36     while(*p!='\0') 37     { 38         p++; 39     } 40     return int(p-A); 41 } 42  43 void strcpn(char * a,const char * b,int len)           //注意b里没有‘\0’，a的长度实际为len+1,多了'\0' 44 { 45     while(len>0) 46     { 47         *a=*b; 48         a++; 49         b++; 50         len--; 51     } 52     *a='\0'; 53 } 54  55 char * strjoin(const char * a, const char * b,int lenb) 56 { 57     char * tmp; 58     int lena=strleng(a); 59     if(a==NULL) 60     { 61         tmp= new char[lenb+1]; 62         strcpn(tmp,b,lenb); 63     } 64     else 65     { 66         tmp=new char[lena+lenb+2];              //长度为 lena加lenb多了一个空格和一个'\0' 67         strcpn(tmp,a,lena); 68         *(tmp+lena)=' '; 69         strcpn(tmp+lena+1,b,lenb); 70         delete[] a; 71     } 72     return tmp; 73 } 74      75 int canMatch(const char * input ,const char * rule)            //返回最大匹配个数，递归函数 76 { 77     if(*rule=='\0')                       //rule必须在input的前面判断啊，啊啊啊啊 78         return 0; 79     if(*input=='\0') 80         return -1; 81     int r=-1,may;                    //r为该次返回值，may没往后的递归返回值，r根据may最中取值 82     if(*rule=='*') 83     { 84         r=canMatch(input,rule+1); 85         if(*input!='\0') 86         { 87             may=canMatch(input+1,rule); 88             if(may>=0&&++may>r) 89                 r=may; 90         } 91     } 92     if(*rule=='?'||*rule==*input) 93     { 94         may=canMatch(input+1,rule+1); 95         if(may>=0&&++may>r) 96             r=may; 97     } 98     return r; 99 }100 101 char * my_find(const char * input ,const char * rule)102 {103     int len=strleng(input);104     int * match=new int[len];        //match[i],记录匹配数例如：input:aabbddf rule:a*d output:aabbdd match为：6，5，-1，-1，-1，-1，-1，所以要记录最大的105     int maxpos=0;    106     char * result=NULL;107     for(int i=0;i
       
        match[maxpos])111             maxpos=i;112     }113     if(match[maxpos]<=0)              //不存在匹配,必须的有才行，开始都错了114     {115         result=new char;116         result[0]='\0';117         return result;118     }119     for(int i=0;i
        
         dp[i][j])173                     dp[i][j]=dp[i-1][j]+1;174             }175             else if(rule[j-1]=='?')176             {177                 if(dp[i-1][j-1]!=-1)178                     dp[i][j]=dp[i-1][j-1]+1;179                 else180                     dp[i][j]=-1;181             }182             else183             {184                 if(dp[i-1][j-1]!=-1&&input[i-1]==rule[j-1])185                     dp[i][j]=dp[i-1][j-1]+1;186                 else187                     dp[i][j]=-1;188             }189         }190         int m=-1;191         int count_ans=0;192         int * ans=new int[len_input];193         char * result=NULL;194         for(int i=1;i<=len_input;i++)195         {196             if(dp[i][len_rule]>m)197             {198                 count_ans=0;                       //因为要找最大的，所以每次发现都将count_ans置为0199                 m=dp[i][len_rule];200                 ans[count_ans++]=i-m;             //更新ans[0]的值,然后count_ans等于1201             }202             else if(dp[i][len_rule]!=-1&&dp[i][len_rule]==m)            //有多个等于m的情况，说明有多个203             {204                 ans[count_ans++]=i-m;                  //count_ans更新，并且记录起始位置205             }206         }207         if(count_ans!=0) 208         {209             for(int i=0;i