P2536 [AHOI2005]病毒检测

记模板串为s2,待测串为s1。

1. 对于s2首尾，若没有，直接一位位匹配直到有即可。

2. 再考虑s2串为的情况。其中是的某个片度。

   我们将依次从s1的合法位置开始向后匹配。（合法位置初始为0）

   用匹配到的第一个位置来更新合法位置。

   至于为什么不用s1后面的位置，这是因为用后面的一定不会比用前面的更优。

   直到匹配完s2，匹配结束。若任何一步匹配失败，则不是病毒。

   注：这种方法不需要限定AGCT。下面的例子也没有限定。

匹配的话用kmp可以做到，但是对于‘?’貌似不好处理。

写的kmp愣是没过。后来打的暴力匹配，没想到比kmp还快......

#include<iostream>
#include<memory.h>
#include<string>
#define maxn 1010
using namespace std;

string s2,s[maxn];
int next1[maxn<<1];
int pipei(string s1,int st,int l,int r){
//在s1的st到lon中查找第一个匹配s2的l到r位的位置hou yi wei
    //暴力匹配
    for(int i=st;i+r-l<s1.length();i++){
    for(int j=l;j<=r;j++){
        if(s1[i+j-l]!=s2[j]&&s2[j]!='?')goto End;
        if(j==r)return i+j-l+1;
    }
    End:continue;
    }
    return -1;

    //kmp

    /*memset(next1,0,sizeof(next1));
    next1[0]=next1[1]=0;int k=0;
    for(int i=l+1;i<=r;i++){
        while(k&&(s2[k+l]!=s2[i]&&s2[k+l]!='?'))k=next1[k];
        next1[i-l+1]=(s2[k+l]==s2[i]||s2[k+l]=='?')?++k:0;
    }k=0;
    for(int i=st;i<s1.length();i++){
        while(k&&s2[k+l]!=s1[i]&&s2[k+l]!='?')k=next1[k];
        k+=(s2[k+l]==s1[i]||s2[k+l]=='?');
        if(k==r-l+1)return i+1;
    }
    return -1;*/
}
bool check(string ss){
    int shou=0,wei1=ss.length(),wei2=s2.length();
    while(s2[shou]!='*'){
        if(s2[shou]!=ss[shou]&&s2[shou]!='?')return true;
        shou++;
        if(shou==wei2)return wei1!=wei2;
        if(shou==wei1){
            for(int i=shou;i<wei2;i++)
            if(s2[i]!='*')return true;
            return false;
        }
    }
    while(s2[wei2-1]!='*'){
        if(s2[wei2-1]!=ss[wei1-1]&&s2[wei2-1]!='?')return true;
        wei1--;wei2--;
        if(shou==wei1){
            for(int i=shou;i<wei2;i++)
            if(s2[i]!='*')return true;
            return false;
        }
    }int st=shou;
    //cout<<shou<<' '<<wei1<<' '<<endl<<shou<<' '<<wei2<<endl;
    while(1){
        if(shou==wei2-1)return false;
        for(int i=shou+1;i<wei2;i++)
        if(s2[i]=='*'){
           if(shou+1==i){
               shou++;
               continue;
           }
            st=pipei(ss,st,shou+1,i-1);
            if(st==-1)return true;
            shou=i;
            break;
        }
    }
}
int main(){
    int n,Ans=0;
    cin>>s2;cin>>n;
    for(int i=1;i<=n;i++){
        string ss;cin>>ss;
        Ans+=check(ss);
    }
    cout<<Ans;
    return 0;
}