无题目传送门。

大致题意:

给定密文明文,密文的每个单词被通过固定的规则(一对一映射)转换成了明文中的一部分(保证存在),求密文在明文中首次出现的位置。

举个例子,密文abbc就在qweerrr中标粗部分出现。

明文和密文不超过$10^6$个单词。

点击获取样例输入输出

注:'$'字符为输入结束标志,不计入明文和密文。

样例输入

a a a b c d a b c $
x y $

xyz abc abc xyz $
abc abc $

a b c x c z z a b c $
prvi dr prvi tr tr x $

样例输出

3

2

3

前置知识:


Solution

很妙的一道KMP,考场上口胡出来居然还对了。

首先很明显是一道单模字符串匹配的题目,自然想到KMP,但是拿什么来KMP?

我们要找到在能够匹配成功的两部分的共性,从而利用这些信息去完成通用的匹配。

  • 什么情况下才能匹配?

当这两段相对的字母出现顺序是相同的。

以aabba和zxxccxa为例。

image.png

aabbaxxccx的字母出现顺序都是形似11221的。

易得这匹配的两段中,相同字符与前一个的相对位置是相同的。

什么意思呢?我们把aabba和xxccx这两个拿来改写成这种形式。如果前面没有相同字符,以$INF$补齐。

aabba中,第二个位置上的a指向一个位置,第四个位置上的b指向一个位置,第五个位置上的a指向第三个位置。那么表示为INF 1 INF 1 3

xxccx中,第二个位置上的x指向一个位置,第四个位置上的c指向一个位置,第五个位置上的x指向第三个位置。那么表示为INF 1 INF 1 3

发现了吗,在这样的表达下,需要匹配的两部分是完全一致的,可以一次KMP跑出来。

完结撒花~~


假的。

考虑另外一组样例aabbc与zxxcczx。

再按照上面表达出来,发现一个是INF 1 INF 1 INF,另一个是INF 1 INF 1 5

那难道这个算法就不可行了吗?

当然不是。

以以上方法记录文本串和模式串的信息分别到txt[]pat[]中。

再仔细看看不同的地方,一个是INF,一个是5。回忆用这个表示的是与前一个相同字符之间的间隔。模式串里的INF表示在模式串中,前面不存在这个字符了。文本串里的5,表示的是上一个相同字符出现在5个位置前。让我们把目光转向文本串此时的5个位置前,发现这个z根本不在xxccz的范围之内。

对应到kmp时的指针j来说,也就是j-txt[i]≤0了。此时的txt[i]我们需要将其视作INF。

然后稍微改亿下kmp判断等与不等的条件即可。

code:

#include<bits/stdc++.h>
using namespace std;
int txt[1000010],pat[1000010];
const int INF=1e9;
map<string,int> last; 
string a;
int n,m;
void init()
{
    while(1)
    {
        n++;
        cin>>a;
        if(a[0]=='$')break;
        if(!last[a])last[a]=n,txt[n]=INF;
        else txt[n]=n-last[a],last[a]=n;
    }
//    for(int i=1;i<=8;i++)
//        printf("%d\n",txt[i]);
    last.clear();
    while(1)
    {
        m++;
        cin>>a;
        if(a[0]=='$')break;
        if(!last[a])last[a]=m,pat[m]=INF;
        else pat[m]=m-last[a],last[a]=m;
    }
    n--,m--;
}
int nxt[1000010];
int main()
{
    init();
    int j=0;
    for(int i=2;i<=m;i++)
    {
        while(j!=0&&pat[i]!=pat[j+1])j=nxt[j];
        if(pat[i]==pat[j+1])j++;
        nxt[i]=j;
    }
    j=0;
    for(int i=1;i<=n;i++)
    {
        while
        (
            j!=0&&
            (
                (pat[j+1]==INF&&j+1-txt[i]>0)||
                (pat[j+1]!=INF&&pat[j+1]!=txt[i])
            )
        )j=nxt[j];//不匹配的情况 
        if(txt[i]==pat[j+1]||(pat[j+1]==INF&&j+1-txt[i]<=0))j++;
        if(j==m)
        {
            printf("%d\n",i-m+1);
            return 0;
        }
    }
    return 0;
}
最后修改:2020 年 08 月 28 日 07 : 42 AM