M_sea

洛谷2536 [AHOI2005]病毒检测
Luogu算法暴力DP。用$f[i][j]$表示模版匹配到$i$、$RNA$匹配到$j$能不能匹配。然后:若$vi...
扫描右侧二维码阅读全文
04
2018/02

洛谷2536 [AHOI2005]病毒检测

Luogu

算法

暴力DP。

用$f[i][j]$表示模版匹配到$i$、$RNA$匹配到$j$能不能匹配。
然后:

  • 若$virus[i]=*$,直接匹配。
  • 否则,考虑这两个能不能匹配,再考虑需不需要通配前面。

细节见代码。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
typedef int mainint;
#define int long long
using namespace std;
char virus[1010],now[510];
int n,lenv,lenn,ans=0;
bool f[1010][510];
int last[510]; //第i位的*匹配到的最早字符 
inline void DP() { //如果now是病毒,ans++ 
    memset(f,0,sizeof(f));
    memset(last,0x3f3f3f3f,sizeof(last));
    f[0][0]=1; //边界
    for (re int i=1;i<=lenv;i++) {
        if (virus[i]=='*') { //*号直接配 
            if (i==1) f[1][0]=1; //特判 
            for (re int j=1;j<=lenn;j++)
                if (f[i][j-1]||f[i-1][j]) {
                    f[i][j]=1;
                    last[i]=min(last[i],j);
                }
        }
        else {
            for (re int j=1;j<=lenn;j++) {
                if (virus[i]!=now[j]&&virus[i]!='?') continue;
                if (f[i-1][j-1]) f[i][j]=1; //考虑是否可以直接配 
                else if (i>1&&virus[i-1]=='*'&&last[i-1]<j) f[i][j]=1;
            }
        }
    }
    if (f[lenv][lenn]) ans++;
}        
mainint main() {
    ios::sync_with_stdio(false);
    cin>>virus+1; lenv=strlen(virus+1); cin>>n;
    for (re int i=1;i<=n;i++) {
        cin>>now+1; lenn=strlen(now+1);
        DP();
    }
    cout<<n-ans<<endl;
    return 0;
}
最后修改:2018 年 11 月 30 日 09 : 43 PM

发表评论