Anonymous

#include <iostream>#include <string>#include <vector>#include <algorithm>#include <map>#include <stack>#include <sstream>#include <deque>#include <queue>#include <cmath>#include <numeric>#include <cstdio>#include <cstdlib>#define INF 100000000using namespace std;string regx1,regx2;int len1,len2;int M[501][501];int Len[501][501];string getStr(string s,int from,int to){    string res="";    for(int i=from;i<to;i++){        if(s[i]!='*'){            res+=(s[i]=='?'?'A':s[i]);        }        }        return res;}    int solve(int s1,int s2){    if(s1==len1&&s2==len2){        Len[s1][s2]=0;        return 0;    }        int &len=Len[s1][s2];    int &m=M[s1][s2];        if(m){        return len;    }        m=1;    if(s1==len1-1&&regx1[s1]=='*'){        len=0;        for(int i=s2;i<len2;i++){            if(regx2[i]!='*') {                len++;            }            }         return len;    }        if(s2==len2-1&&regx2[s2]=='*'){        len=0;        for(int i=s1;i<len1;i++){            if(regx1[i]!='*') {                len++;            }            }        return len;    }          if(s1==len1||s2==len2) { return INF;    }         if((regx1[s1]=='?'&&regx2[s2]!='*')||(regx2[s2]=='?'&&regx1[s1]!='*')||(regx1[s1]=='?'&&regx2[s2]=='?')||(regx1[s1]==regx2[s2]&&regx1[s1]!='*')){        Len[s1][s2]=solve(s1+1,s2+1)+1;        return Len[s1][s2];    }     len=INF;    if(regx1[s1]=='*'){        for(int i=s2;i<len2;i++){            if(solve(s1+1,i)!=INF){                int strln=i-s2+solve(s1+1,i);                if(strln<len){                    len=strln;                }                }            }        }    if(regx2[s2]=='*'){        for(int i=s1;i<len1;i++){            if(solve(i,s2+1)!=INF){                int strln=i-s1+solve(i,s2+1);                if(strln<len){                    len=strln;                }                }            }        }    return len; }string construct(){    int start1=0,start2=0;    string res="";    while(start1<len1&&start2<len2){        if(start1==len1-1&&regx1[start1]=='*'){            res+=getStr(regx2,start2,len2);            start2=len2,start1=len1;        }        else if(start2==len2-1&&regx2[start2]=='*'){            res+=getStr(regx1,start1,len1);            start2=len2,start1=len1;        }        else if(regx1[start1]==regx2[start2]&&regx2[start2]!='*'){            if(regx1[start1]=='?'&&regx2[start2]=='?'){                res+='A';            }            else if(regx2[start2]=='?'){                res+=regx1[start1];            }            else{                res+=regx2[start2];            }start1++,start2++;          }        else if(regx1[start1]=='?'&&regx2[start2]!='*'){            res+=regx2[start2];            start1++,start2++;        }        else if(regx2[start2]=='?'&&regx1[start1]!='*'){            res+=regx1[start1];            start1++,start2++;        }        else{            int minLen=INF;            int tIndex=-1;            int flag=0;            if(regx1[start1]=='*'){                          for(int i=start2;i<len2;i++){                    if(solve(start1+1,i)!=INF){                        if(minLen>(Len[start1+1][i]+i-start2)){                            tIndex=i;                            minLen=Len[start1+1][i]+i-start2;                            flag=1;                        }                        }                    }                }            if(regx2[start2]=='*'){                for(int i=start1;i<len1;i++){                    if(solve(i,start2+1)!=INF){                        if(minLen>(Len[i][start2+1]+i-start1)){                            tIndex=i;                            minLen=Len[i][start2+1]+i-start1;                            flag=2;                        }                        }                    }                }            if(flag==1){                res+=getStr(regx2,start2,tIndex);                start1++;                start2=tIndex;            }else if(flag==2){                res+=getStr(regx1,start1,tIndex);                start2++,start1=tIndex;            }            }          }        return res;}      int main(){    cin>>regx1>>regx2;    len1=regx1.length(),len2=regx2.length();    memset(M,0,sizeof(M));    for(int i=0;i<501;i++) for(int j=0;j<501;j++) Len[i][j]=INF;            printf("%s\n",((solve(0,0)<INF)?construct().c_str():"#"));     }