2024“钉耙编程”中国大学生算法设计超级联赛（1）第一场1001

循环位移题解

2024“钉耙编程”中国大学生算法设计超级联赛（1）

题目：

Problem Description

定义字符串 S=S0+⋯+Sn−1 循环位移 k 次为 S(k)=Skmodn+⋯+Sn−1+S0+⋯+S(k−1)modn。

定义 [A]=\setA(k),k∈N.

给出 T 组串 A,B，询问 B 有多少个子串在 [A] 中。

Input

第一行一个 T 表示输入组数。

接下来每行两个字符串，表示 A 和 B，保证 |A|≤|B|。

保证 ∑|B|≤1048576.，并且字符串均由大写字母组成。

Output

输出 T 行，每行一个数表示答案。

Sample Input

3
AN MANTLEFAN
MVP XPTIJMVPMVP
CJMR JDRCJMRAJMRCJMGC

Sample Output

2
4
5

Hint:

第一个样例：MANTLEFAN,MANTLEFAN第三个样例：JDRCJMRAJMRCJMGC,JDRCJMRAJMRCJMGC,JDRCJMRAJMRCJMGC,JDRCJMRAJMRCJMGC,JDRCJMRAJMRCJMGC

先考虑到将A所有情况放入map中接着将b中所有长度等于A的字符串拿出来查找:

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t;
    unordered_map<string,bool>check;
    cin>>t;
    while(t--)
    {
        string a,b;
        cin>>a>>b;
        string fr,be;
        for(int i=0;i<a.size();i++)
        {
            fr=a.substr(0,i);
            be=a.substr(i,a.size()-i);
            check[be+fr]=true;
        }
        int ans=0;
        for(int i=0;i+a.size()-1<b.size();i++)
        {
            if(check[b.substr(i,a.size())])
            {
                ans++;
                check.erase(b.substr(i,a.size()));
            }
        }
    }
    return 0;
}

发现MLE了

考虑用字符串哈希进行优化,暴力计算字符串对应的值会发现时间复杂度过高,交了一发超时了
通过字符串前缀和进行优化,但优化完会发现数据卡了经典模数的哈希碰撞,有重复值产生
解决方案 { 尝试不同模数 双哈希 解决方案 \begin{cases} 尝试不同模数\\ 双哈希 \end{cases} 解决方案{尝试不同模数双哈希​
队友交了一发模数99999999过了
或者用双哈希减少碰撞几率,即双重验证,对两个不同的数取模,只有同时相等才视作相等

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define ull unsigned long long
#define mod (1610612741)
#define mod2 (163227661)

ll fastpow(ll a, ll b) {
    ll sum = 1;
    while (b) {
        if (b & 1) {
            sum = sum * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return sum;
}
ll fastpow2(ll a, ll b) {
    ll sum = 1;
    while (b) {
        if (b & 1) {
            sum = sum * a % mod2;
        }
        a = a * a % mod2;
        b >>= 1;
    }
    return sum;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t;
    unordered_map<ll,bool>check;
    unordered_map<ll,bool>check2;
    cin>>t;
    while(t--)
    {
        int ans=0;
        string a,b;
        cin>>a>>b;
        vector<ll>sum(a.size());
        vector<ll>sum2(a.size());
        sum2[0]=sum[0]=(ll)a[0];
        ll key=0,key2=0;
        for(int i=1;i<a.size();i++)
        {
            sum[i]=((sum[i-1]*127)%mod+a[i])%mod;
            sum2[i]=((sum2[i-1]*127)%mod2+a[i])%mod2;
        }
        for(int i=0;i<a.size();i++)
        {
            //190089->190 089->089 190(sum[i])->089=190089-190000(sum[size]-sum[i]*127^089.size()
            check[((sum[a.size()-1]-sum[i]* fastpow(127,a.size()-1-i)%mod+mod)%mod*fastpow(127,1+i)+sum[i])%mod]=true;
            check2[((sum2[a.size()-1]-sum2[i]* fastpow2(127,a.size()-1-i)%mod2+mod2)%mod2*fastpow2(127,1+i)+sum2[i])%mod2]=true;
        }

        vector<ll>sumb(b.size());
        vector<ll>sumb2(b.size());
        sumb[0]=(ll)b[0];
        sumb2[0]=(ll)b[0];
        for(int i=1;i<b.size();i++)
        {
            sumb[i]=((sumb[i-1]*127)%mod+b[i])%mod;
            sumb2[i]=((sumb2[i-1]*127)%mod2+b[i])%mod2;

        }
        key=sumb[a.size()-1];
        key2=sumb2[a.size()-1];
        if(check[key]&&check2[key2])ans++;
        for(int i=0;i+a.size()<b.size();i++)
        {
            key2=(sumb2[i+a.size()]-(sumb2[i]* fastpow2(127,a.size()))%mod2+mod2)%mod2;
            key=(sumb[i+a.size()]-(sumb[i]* fastpow(127,a.size()))%mod+mod)%mod;
            if(check[key]&&check2[key2])ans++;
        }
        cout<<ans<<"\n";
    }

    return 0;
}