题解 P2635 【带通配符的字符串匹配】

加里纳利 · 2015-10-10 14:26:07 · 题解

另放上出题者dropD的C++源代码。

#include<iostream>
#include<cstring>
using namespace std;
int f[3005][3005]={0},q[3005]={0},prt[3005][3005]={0};
string st1,st2;
int gcd(int a,int b)
{   if(b==0)return a;
    return gcd(b,a%b);
}
void Get(int x,int y)
{   if(x==0&&y==0)return;
    int lx=x-1,ly=prt[x][y];
    if(st1[x]=='*'&&y!=ly){q[++q[0]]=y-ly;}
    Get(lx,ly);
}
int main()
{   cin>>st1>>st2;
    int i,j,k,bj,div,ans=0,len1=st1.length(),len2=st2.length();
    st1=' '+st1;st2=' '+st2;
    f[0][0]=1;
    for(i=1;i<=len1;i++)
       for(j=0;j<=len2;j++)
         {if(st1[i]=='?'||st1[i]==st2[j])
            {f[i][j]=f[i-1][j-1];
             if(f[i][j])prt[i][j]=j-1;
            }
          else if(st1[i]=='*')
            {for(k=j,bj=0;k>=0;k--)
                if(f[i-1][k]){bj=1;break;}
             if(bj){f[i][j]=1;prt[i][j]=k;}
            }
         }
    if(f[len1][len2])
      {cout<<"matched\n";
       for(i=1;i<=len1;)//处理?匹配符 
         {j=i;
          while(st1[j]=='?')j++;
          if(i!=j)q[++q[0]]=j-i;
          i=j+1;
         }
       Get(len1,len2);//递归处理*匹配符 
       if(q[0]==0)cout<<0;
       else if(q[0]==1)cout<<1;
       else if(q[0]>=2)
         {div=gcd(q[1],q[2]);
          for(i=3;i<=q[0];i++)div=gcd(div,q[i]);
          for(i=1;i<=q[0];i++)ans+=q[i]/div;
          cout<<ans;
         } 
      }
    else cout<<"not matched";
    return 0;
}
思路完全一样