题目传送门:https://ac.nowcoder.com/acm/contest/9984/B

思路

题意是找出字符串$t$的前缀,使之由字符串$s$的两个前缀组成,即$t_{i+j}=s_i+s_j$,求满足条件的总对数。

首先根据前缀的特性不难想到,必须要有$t_i=s_i$,这是必要条件。那么枚举$s$和$t$的所有相同前缀$s_i$,然后求$t-s_i$,找其能匹配上$s$的前缀$s_j$的最大长度,计入答案即可。

具体算法就是哈希和二分:

  • 哈希能够O(1)判断两个子串是否匹配(字符串哈希算法

  • 二分是因为我们在找到某个前缀匹配时,前缀的前缀也一定匹配,所以可以二分找到最长前缀,因为比它长的前缀都不匹配,比它短的所有前缀都匹配,这就满足二分使用前提的单调性。

举个例子:

s串:aab
t串:aaab

枚举i=1,有相同前缀$s_i$为'a',$t-s_i$为'aab',最长能匹配上$s$的前缀为'aab',其长度为3,答案+3。

枚举i=2,有相同前缀$s_i$为'aa',$t-s_i$为'ab',最长能匹配上$s$的前缀为'a',其长度为1,答案+1。

枚举i=3,没有相同前缀('aab' != 'aaa'),结束,答案为4。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll; // ull自动溢出,相当于对2^64取模
const int N=1e5+10,bas=131; // bas自定,只要能尽量避免哈希冲突
int n1,n2;
ll sum1[N],sum2[N],p[N]; // sum1,sum2存哈希的前缀和,p[i]=bas^i
char s1[N],s2[N];
ll has1(int l,int r) // O(1)得到[l,r]区间内sum1的哈希值
{
    return sum1[r]-sum1[l-1]*p[r-l+1];
}
ll has2(int l,int r)
{
    if(r>n2)return 0;
    return sum2[r]-sum2[l-1]*p[r-l+1];
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>s1+1>>s2+1;
    n1=strlen(s1+1);
    n2=strlen(s2+1);
    sum1[0]=sum2[0]=0;p[0]=1;
    for(int i=1;i<=max(n1,n2);i++)
    {
        if(i<=n1)sum1[i]=sum1[i-1]*bas+s1[i];
        if(i<=n2)sum2[i]=sum2[i-1]*bas+s2[i];
        p[i]=p[i-1]*bas; // p[i]=bas^i
    }
    ll ans=0;
    for(int i=1;i<=n2-1;i++) // 第2个字符串减去相同前缀[1,i]
    {
        if(s1[i]!=s2[i])break;
        if(s2[i+1]!=s1[1])continue; // 剩下的第2个字符串连第1个字符都匹配不上
        int l=1,r=n1,tmp=0;
        while(l<=r)
        {
            int mid=(l+r)/2; // 假设长度为mid
            ll t1=has1(1,mid); // 第1个字符串前缀哈希值
            ll t2=has2(i+1,i+mid); // 第2个字符串剩余前缀哈希值
            if(t1==t2)tmp=mid,l=mid+1; // 匹配上了,长度继续变大
            else r=mid-1;
        }
        ans+=tmp;
    }
    printf("%llu\n",ans);
    return 0;
}
/*
aaaaaabbb
aaaaaaaaaaa
ans:35

aaaaa
aaaa
ans:6

aaaa
aaaaa
ans:10

abcdabcd
abcd
ans:0

abcd
abcdabcd
ans:4

abc
aab
ans:2
*/

后记

当时没好好学哈希,以为unordered_map就能代替相同功能,然而碰到这题就束手无策了,问了yz大佬才搞懂思路,我自己写还wa了5发,真的菜哭了QAQ