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*
 
 */

博主蒟蒻可以随意转载但要附上本文链接广告位招租