抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >
转移自老blog

hdu6170

题目大意 :
         类似正则匹配

         这个题开始的时候没有写出来,想到了状态的设法,如果设dp[i][j]代表第一个串的前i项能否匹配第二个串的前j项,状态个数很明显是n2的,然而一直苦于*符号的匹配,找不到好的转移方程,不管怎么想都是n3的转移复杂度,当s2[j]是*的时候,dp[i][j] <-dp[pre][j] 其中pre可以取的值的要求是:对于所有的pre<=k<=i s1【k】=s1【i】
         这个转移不是不可以优化,这显然是一个连续的区间,可以采取rmq预处理来实现降低时间复杂度到n2lgn,但是这样写似乎显得小题大做,并且时间复杂度不是很理想,可能卡在时间的边界上然后time limited。
         最后看了题解,发现可以O(1)转移,但是网上的题解的证明过程显得苍白无力,甚至有不少代码是错的,ac不过是因为数据弱而已。
         我想了很久,最终得到了*的转移: 考虑s1[i]和s1[i-1]是否相等,如果不相等的话,那么*要么贡献0次由dp[i][j-2]转移,要么贡献1次由dp[i][j-1]转移,复杂的是相等的情况,*贡献0次和1次是一样的,因为s1[i]和s1[i-1]相等,所以*可能贡献多次(多指的是大于等于二)。
         分析贡献多次的时候:从dp[i][j]=1必要条件入手,因为多次,所以如果他少贡献一次的话,dp[i-1][j]也为1,且有条件s1[i-1]=s2[j-1]或s2[j-1]=='.'。
         然后证明此必要条件的充分性,由于dp[i-1][j]=1且s1[i-1]和s2[j-1]是一样的,那么*多贡献一次就可以了。因为s1[i-1]和s2[j-1]是一样的,所以可以多贡献一次。
         于是(dp[i-1][j]=1且s1[i-1]和s2[j-1]一样)与(贡献多次的dp[i][j]=1)等价。
         这前的每一个细节都很重要,为什么要求s1[i-1]和s2[j-1]是一样的,如果不做此要求,就过不了这个例子:
aa
ab*
         至于dp边界的处理,特别简单,我们改变输入数据s1 和s2为(“@@”+s1)和(“@@”+s2),边界就特别特别简单了。
         虽说简单,但我还是搞错了,忽略了一种情况因为少了下面的代码,
         然后就过不了这个反例
c
a*b*c
         因为什么呢?因为”@@”居然可以和”@@a*”匹配,简直是恐怖。
#include<bits/stdc++.h>
using namespace std;

int main(){
    int T;
    scanf("%d ",&T);
    while(T--){
        static const int maxn=2600;
        static char s1[maxn],s2[maxn];
        static int dp[maxn][maxn];
        //scanf("%s%s",s1+2,s2+2);
        gets(s1+2);
        gets(s2+2);
        s1[0]=s2[0]=s1[1]=s2[1]='@';
        int l1=strlen(s1);
        int l2=strlen(s2);
        dp[0][0]=dp[1][1]=1;
        for(int j=2;j<l2;j++){
            if(s2[j]=='*')dp[1][j]=dp[1][j-2];
            else dp[1][j]=0;
        }

        for(int i=2;i<l1;i++){
            for(int j=2;j<l2;j++){
                if(s2[j]=='.')dp[i][j]=dp[i-1][j-1];
                else if(s2[j]=='*'){
                    if(s1[i]!=s1[i-1]){//最多贡献一次
                        dp[i][j]=dp[i][j-2]||dp[i][j-1];
                    }
                    else{
                        dp[i][j]=dp[i][j-2]||dp[i][j-1]||(dp[i-1][j]&&(s1[i-1]==s2[j-1]||s2[j-1]=='.'));
                    }
                }
                else dp[i][j]=dp[i-1][j-1]&&s1[i]==s2[j];
            }
        }

        cout<<(dp[l1-1][l2-1]?"yes":"no")<<endl;
    }
}

/*
 
 --------aa
 --------ab*
 
 */

评论