题解 | L、字符串

L、字符串

前置知识：字符串哈希

我们判断两个十进制的数是否相等，可以如下来拆分操作： 先判断个位数是否一样，再判断十位数是否一样……最后判断最高位是否一样，如果全部一样那么这两个十进制数就是一样大的。设个位数是a，十位数是b……最后一位数是z，那么这个数的大小就是：(a* 10^0)+(b * 10^1)+……+(z * 10^n).只要这个数相等，那么这两个十进制数也是相等的。

这个其实就是字符串哈希的原理。我们可以把字符串转化成一个base进制的数，只要两个字符串转化成的数相同，那我们就认为这两个字符串是相等的。但base必须是一个质数，才能保证正确性。

问题解析

记录下s的长度为len，我们可以先把字符串s转化成一个base进制的数（这里我选的base是13331）。

然后我们可以把两个s首尾相连起来，也对它求一次字符串哈希。

因为我们把两个s首尾相连了，这样把前k个字符放到最后面的操作就变成了区间[k,k+len-1]的字符串。我们只要用前缀和求[k,k+len-1]的字符串哈希值，判断和s的哈希值是否一样，我们就能知道这两个字符串是否相等了。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

//#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e7 + 50, MOD = 1e11 + 3;
int p=99971,base=13331;
int qpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)res = (1LL) * res * a % MOD;
        b >>= 1;
        a = (1LL) * a * a % MOD;
    }
    return res;
}

//获取l~r这一段字符串的字符串哈希值
ull get_hash(vector<ull>&v,int l,int r,vector<ull>&bpow)
{
    ull t=v[l-1]*bpow[r-l+1];
    return (v[r]-t);
}

void solve()
{
    int n;
    string s;
    cin >> n >> s;
    string str=s+s;
    int m=str.size();
    vector<ull>v(m+1),bpow(m+1,1);
    ull res=0;
    //初始化字符串哈希值
    for(int i=1;i<=m;i++)
    {
        res=(res*base+str[i-1]);
        v[i]=res;
        bpow[i]=bpow[i-1]*base;
    }
    int k=1,cnt=0;
    //1到n部分的字符串就是原本的字符串s
    ull y=get_hash(v, 1, n, bpow);
    while(k<=n)
    {
        
        ull x=get_hash(v, k+1, k+n, bpow);
        //两个字符串哈希值相等，则这两个字符串相等
        if(x==y)cnt++;
        k++;
    }
    cout<<cnt<<endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}