马东什么?

又是一个大家看过无数遍的笑话。

夏洛:大爷,楼上322住的是马冬梅家吧?

大爷:马冬什么?

夏洛:马冬梅。

大爷:什么冬梅?

夏洛:马冬梅啊。

大爷:马什么梅?

夏洛:行,大爷你先凉快着吧。

大爷:好嘞。

虽然看过了无数遍,但其实里面仍然有很多东西值得发掘。假如夏洛说了一大段话,而大爷永远听不清楚一个完整的“马冬梅”,只能听到一些”马东?“,”马?梅“,“?东梅”之类的词语。其中”?”代表任意字。

也就是说,只要夏洛说出“马东”两个字,在后面还有内容的情况下,无论后面那个字是什么,都当成大爷听到了“马冬?”三个字,就是相当于大爷听到了“马东梅”。

现在假设夏洛说了一段话,求大爷听到“马东?”,“马?梅”,“?东梅”,这类词的不同种数,其中”?”代表任意字。

比如夏洛说:东梅马东东梅一二三四马五梅马东。

那么大爷就可以分别听到一遍“马东?”,“?东梅”,“马?梅”。

换成计算机语言,就得简化一下。

给出一些模式串,包含小写字母和一个”.”,”.”可能在模式串种任意位置,后者可以代表任意小写字母。再给出一个文本串,求文本串,出现了多少不同种类的模式串。

解法很简单,AC自动机暴力即可。

不过要是模式串中有很多”.”,暴力就会爆炸。至于怎么改我还没想到。

#include<bits/stdc++.h>
#define N 500010
using namespace std;
queue<int>q;
int n,m,ans = 0;
char p[1000],tex[1000];
struct aho
{
    int c[N][26],val[N],fail[N],cnt=0;//初始话为0
    void ins(char *s)
    {
        int len = strlen(s);
        int now = 0;
        for(int i=0; i<len; i++)
        {
            int v = s[i] - 'a' +1;
            if(!c[now][v])
                c[now][v] = ++cnt;
            now = c[now][v];
        }
        val[now] = 1;
    }
    void build()
    {
        for(int i=1; i<=26; i++)
        {
            if(c[0][i])
                fail[i]] = 0,q.push(c[0][i]);

        }
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            for(int i=1; i<=26; i++)
            {
                if(c[u][i])
                {
                    fail[i]] = c[fail[u]][i];
                    q.push(c[u][i]);
                }
                else
                {
                    c[u][i] = c[fail[u]][i];
                }
            }
        }
    }
    int query(char *s)
    {
        int len = strlen(s);
        int now = 0,ans = 0,v;
        for(int i=0; i<len; i++)
        {
            now = c[now][s[i]-'a'+1];
            //printf("now = %d\n");
            for(int t = now; t && val[t] ; t = fail[t])
            {
                ans++;
                val[t] = -1;
            }
        }
        return ans;
    }

} Accept;
//马冬梅
int main()
{
    int len;
    char ss[N];
    int num;
    scanf("%d",&num);
    for(int i=1; i<=num; i++)
    {
        scanf("%*c%s",p);
        strcpy(ss,p);
        len = strlen(p);
        for(int j=0; j<len; j++)
        {
            if(p[j] == '.')
            {
                for(int i=1; i<=26; i++)
                {
                    ss[j] = 'a'+i-1;
                    Accept.ins(ss);
                }
            }
        }

    }
    scanf("%*c%s",tex);
    Accept.build();
    printf("%d",Accept.query(tex));
}

不过要是大爷听得很清楚,但夏洛说得不太清楚呢?或者说大爷昨天带耳机听摇滚歌曲的时候,取下耳机把助听器弄出了了呢?
也就是说,假设夏洛说了一段话,但实际大爷有几个字没听清楚。

比如大爷听到”马东?去上学”,其中?是大爷没听清楚的。

但大爷知道他大概会听到哪些词,比如说”马东梅“,那么由于大爷没听清夏洛说的第三个字,所以夏洛有可能说的是”马东梅“。

假如大爷还认为可能是”马东有“,按照上述推理,夏洛也可能正如大爷说的那样真的说的是”马东有“。

现在大爷听到了一段话,有一些字没听清,大爷觉得这个夏洛可能说一些词,现在问夏洛可能说的不同种类词的种类数。

翻译成术语就是给出一些模式串,只包含小写字母。以及一个文本串,包含小写字母和”?“,后者表示可能是任意一个小写字母。求文本串中可能出现的不同模式串的种类数。输入文件中用”.”表示”?“。

其实也很简单,只要在query改一点就行了。如果当前文本串中当前的字是不清楚的话,就找其上一个节点,找上一个节点的失配指针,再对所有可能的求26个字母。

int query(char *s)
    {
        int len = strlen(s);
        int now = 0,ans = 0;
        for(int i=0; i<len; i++)
        {
            if(s[i] == '.')
            {

                for(int t = now; t ; t = fail[t])
                {
                    for(int j=1; j<=26; j++)
                    {
                        if(c[t][j] && val[j]])
                        {
                            ans++;
                            val[j]] = -1;
                        }
                    }
                }
                continue;
            }
            now = c[now][s[i]-'a'+1];
            for(int t = now; t && val[t]; t = fail[t])
            {
                ans++;
                val[t] = -1;
            }

        }
        return ans;
    }

还有一种问题,我忘了是什么了,想到了再写吧

2 thoughts on “马东什么?”

Leave a Reply to gaigai Cancel reply