Atcoder 题解

Atcoder Beginner Contest 257 problem G 题解

题目链接:点我

题目大意

给定两个由小写字母构成的字符串$S$和$T$。

求一个最小的$k$，使得字符串$S$的k个前缀子串相连后等于字符串$T$。

如果不存在，则输出$-1$。

样例输入1

aba
ababaab

样例输出1

3

样例解释1

字符串$T$可以被看做$ab+aba+ab$，而$ab$和$aba$是$S$的前缀子串。
字符串$T$不能再被写作两个或以下的子串相连，因此输出$3$。

样例输入2

atcoder
ac

样例输出2

-1

数据范围

• $1 \leq |S| \leq 5 \times 10^5$
• $1 \leq |T| \leq 5 \times 10^5$
• $S$与$T$中的字母均为小写字母。

解析

这到底需要用到$kmp$算法(模式匹配法)，这里不做详细介绍，有兴趣的可以去看其他人的详解博客。

简单来说，$kmp$算法可以快速求出一个数组$ne[i]$，表示一个字符串的前$i$位中的最大前后缀匹配。如，对于字符串$abcdabcef$，则$ne[7]=3$。

对于本题，我们可以将字符串$S$与$T$连接在一起，并且之间用一个字符串中不会出现的字符(如‘#’)来连接。使用$kmp$计算出$ne$数组之后，就丢弃前$|S|+1$个字符。并计算答案。

然后应该想到动态规划。定义$f[i]$表示取$T$中前$i$个字符所得的答案。

有了这个数组，我们便可以得到以下的递推公式:

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
string s,t;
int n,ne[N],f[N],ans=1;
inline void kmp()
{
    int j=-1;
    ne[0]=j;
    for(int i=1;i<s.size();i++){
        while(j>=0&&s[i]!=s[j+1])j=ne[j];
        if(s[i]==s[j+1]) j++;
        ne[i]=j;
    }//详解见其他
}
int main()
{
    cin>>s>>t;
    n=s.size();//找到开始计算答案的地方
    s+='#';s+=t; //将两字符串连接起来，计算ne数组
    kmp(); //kmp算法
    for(int i=n+1;i<s.size();i++){
        if(ne[i]>=0) f[i]=f[i-ne[i]-1]+1; 
        //如果ne[i]>=0，就代表可以从S中找到一个ne[i]这么长的子串前缀来串联
        //减1是减去'#'号所占的位置
        else f[i]=0x3f3f3f3f; //否则不可能拼凑出前i个字符
    }
    if(f[s.size()-1]>=N) cout<<-1;//如果写f[s.size()-1]==0x3f3f3f3f,会WA一个点(震怒)
    else cout<<f[s.size()-1];
}

完结撒花~