洛谷P3167 通配符匹配 [CQOI2014] 字符串

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

正解:哈希+dp/AC自动机/kmp

解题报告:

传送门!

这题解法挺多的,所以就分别港下好了QwQ

首先港下hash+dp趴

可以考虑设dp式f[i][j]:匹配到第i个通配符了,下面那个字符串匹配到第j位了是否可行

转移的话就只要关心两个通配符之间的那一段是否相等就好

那判断相等就应该要想到哈希鸭,就做完了

啊有点儿简洁,,,

思路挺简单的主要细节比较多趴,所以我等下直接放代码好了QwQ

然后说下AC自动机

就先按'*'通配符分成几段,然后对每段独立地分别做

然后下面当每段之间相对独立,说下每段内部怎么做

首先在每段内部,按'?'再分成几段,分别插入AC自动机中,建fail指针balabala不讲

然后就直接把整个儿下面的那个串在AC自动机上跑,然后开个数组cnt[]记录原串上的每个节点作为开头能匹配上这一段的多少个小段

然后再遍历一遍这整个儿串判断下,如果cnt==小段的数量就欧克了

然后这儿注意下,就因为它每次都直接整个儿原串上跑一次,所以还要记录一下上一次在原串上匹配到第几位了,强制在这一位之后匹配

两个小细节注意下

第一个是这个其实用了一个贪心的小思想,即尽量在前面匹配,可以证明这显然是对的,懒得证了挺显然的还QwQ

第二个是特判下开头结尾有没有'*',特殊处理下

还有一个不算细节问题,,,只是随手记下QAQ就开AC自动机本来是互相独立的嘛,但是如果每次重新建就要先清空再balabala的,就很麻烦,所以直接新开一个根节点然后一直接着做就好,overr(好像没有表述好,,,直接看我代码趴QAQ

(打完代码的lq又回来补充了,,,还有一个细节就,我开始打都快打完了,突然脑子一抽,就觉得,好像可以直接开struct{}tr[N],这样分别表示每个AC自动机代码打起来就很简单

然后我就全删了,改改改改

改完之后我突然意识到有个问题,,,就我是写的数组型,然后我并不知道每个串长的上界,只知道所有串长的上界,内存就会爆炸,所以提醒一下不要这么写,,,当然如果你是指针玩家当然麻油关系QAQ

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar()
#define ri register int
#define rb register bool
#define rc register char
#define ll unsigned long long
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)

+;
char ch[N],s[N];
int nod_cnt,cnt[N],n,rt[N],num,str_cnt[N],lst,lin_cnt;
bool bg,ls;
struct node
{
    ],fail;}tr[N];vector<int>ed[N];queue<int>Q;
    il void insert(ri l,ri r,ri id,ri num)
        {
            ri nw=rt[num];
            rp(i,l,r)
            {
                ])tr[nw].to[s[i]-]=++nod_cnt;
                nw=tr[nw].to[s[i]-];
            }
            ed[nw].push_back(id);
        }
    il void get_fail(ri num)
        {
            rp(i,,)if(tr[rt[num]].to[i])Q.push(tr[rt[num]].to[i]),tr[tr[rt[num]].to[i]].fail=rt[num];else tr[rt[num]].to[i]=rt[num];//,printf("to=%d\n",tr[rt[num]].to[i]);
            while(!Q.empty())
            {
                ri nw=Q.front(),sz=ed[tr[nw].fail].size();Q.pop();
                rp(i,,sz-)ed[nw].push_back(ed[tr[nw].fail][i]);
                rp(i,,)
                    if(tr[nw].to[i])Q.push(tr[nw].to[i]),tr[tr[nw].to[i]].fail=tr[tr[nw].fail].to[i];
                    else tr[nw].to[i]=tr[tr[nw].fail].to[i];//,printf("to=%d\n",tr[nw].to[i]);
            }
        }
    il void bd(ri l,ri r,ri num)
        {
            rt[num]=++nod_cnt;
            for(ri i=l;i<=r;++i)
                if(s[i]!='?')
                {
                    ri pos=i;
                    while(pos<=r && s[pos]!='?')++pos;
                    --pos;
                    insert(i,pos,pos-l+,num);
                    ++str_cnt[num];
                    i=pos;
                }
            get_fail(num);
        }
    il bool fd(ri num,ri l,ri r,rb fr,rb nd)
        {
            ri nw=rt[num];memset(cnt,,sizeof(cnt));
            rp(i,,n)
            {
                nw=tr[nw].to[ch[i]-];ri sz=ed[nw].size();
                rp(j,,sz-){)++cnt[i-ed[nw][j]+];}
            }
            rp(i,lst+,n)
            {
                if(cnt[i]==str_cnt[num])
                {
                    )
                    {
                        )continue;
                        if(nd && !ls && i+r-l!=n)continue;
//                        printf("%d\n",lst);
                        lst=i+r-l;;
                    }
                    if(nd && !ls && i+r-l!=n)continue;
//                    printf("%d\n",lst);
                    lst=i+r-l;;
                }
            }
            ;
        }
}tr;

il int read()
{
    rc ch=gc;ri x=;rb y=;
    '))ch=gc;
    ;
    )+(x<<)+(ch^'),ch=gc;
    return y?x:-x;
}

int main()
{
//    freopen("3167.in","r",stdin);//freopen("3167.out","w",stdout);
    scanf();ri lth=strlen(s+);bg=s[]=='*';ls=s[lth]=='*';while(lth && s[lth]=='*')--lth;
    ;i<=lth;++i)if(s[i]!='*'){ri pos=i;while(s[pos]!='*' && pos<=lth)++pos;--pos;tr.bd(i,pos,++lin_cnt);i=pos;}
    ri T=read();
    while(T--)
    {
        scanf();n=strlen(ch+);if(!lth){printf("YES\n");continue;}
        lin_cnt=;rb flg=;lst=;
        ;i<=lth;++i)
            if(s[i]!='*')
            {
                ri pos=i;while(s[pos]!='*' && pos<=lth)++pos;++lin_cnt;--pos;
                ;break;}
                i=pos;
            }
        flg?printf("NO\n"):printf("YES\n");
        }
    ;
}

kmp我麻油get,,,但是听说和AC自动机很像,,,?所以我先把前两个的代码打了然后可能明天或者以后想起来了再想下kmp怎么做,,,想起来了就写想不出来就当没有kmp这个算法TT