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 <iostream> 28 #include <string> 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<len;i++)108     {109         match[i]=canMatch(input+i,rule);110         if(match[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<len;)120     {121         if(match[i]==match[maxpos])   //用相等好，因为有可能有多个match[i]等于最大值，用maxpos就错了122         {123             result=strjoin(result,input+i,match[maxpos]);124             i+=match[maxpos];               //这样就直接跳过了后面匹配的，例如:a(1)a(2)a(3) a(1)a(2),匹配完aa后直接跳过a(2),到a（3）125 //            i++;                                       //这样就会是aa aa ，题目的跳过匹配的原来就是这个意思啊126         }127         else128             i++;129     }130     delete[] match;131     return result;132 }133 134 /*135 方法二：采用动态规划方法dp[i][j]表示字符串1和字符串2分别以i和j结尾匹配的最大长度136 例如：input：abccde  rule：a?c137        a  ?  c138     0  1  2  3 （rule） 139   0 0 -1 -1 -1  140 a 1 0  1 -1 -1141 b 2 0 -1  2 -1142 c 3 0 -1 -1  3143 c 4 0 -1 -1 -1144 d 5 0 -1 -1 -1145 e 6 0 -1 -1 -1146 （input）147 找最后一列的最大的数，即找出以rule最后一个结尾匹配的最大值（例如abccd 和*c,所以要最大值），解决时注意，记录起点和多个的情况148 */149 150 char * my_find2(const char * input,const char * rule)151 {152     if(input==NULL||rule==NULL)153         return NULL;154     int len_input=strleng(input);155     int len_rule=strlen(rule);156     int ** dp=new int * [len_input+1];157     int may;158     for(int i=0;i<=len_input;i++)159         dp[i]=new int[len_rule+1];160     for(int i=1;i<=len_rule;i++)161         dp[0][i]=-1;162     for(int i=0;i<=len_input;i++)163         dp[i][0]=0;164     for(int i=1;i<=len_input;i++)165         for(int j=1;j<=len_rule;j++)166         {167             if(rule[j-1]==‘*‘)                  //注意是j-1而不是i-1168             {169                 dp[i][j]=-1;                      //a*c 和bfc这种情况170                 if(dp[i-1][j-1]!=-1)171                     dp[i][j]=dp[i-1][j-1]+1;172                 if(dp[i-1][j]!=-1&&dp[i-1][j]+1>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<count_ans;i++)210             {211                 result=strjoin(result,ans[i]+input,m);212             }213 214         }215         else          //说明没有匹配的，返回空字符串216         {217             result=new char;218             result[0]=‘\0‘;219         }220         for(int i=0;i<=len_input;i++)221             delete[] dp[i];222         delete[] dp;223         return result;224 }225 226 int main()227 {228     //char  *input="newsadfanewfdadsf";229     //char * rule="new";230     string input[]={"abcadefg","newsadfanewfdadsf","breakfastfood","asdfasdf","aaaaaaa"};231     string rule[]={"a?c","new","f*d","adfe","a"};232     int n=5;233     for(int i=0;i<n;i++)234     {235         cout<<my_find2(input[i].c_str(),rule[i].c_str())<<endl;236     }237     //cout<<my_find(input,rule)<<endl;238     system("pause");239 }