牛客周赛103场F题补题+题解

链接牛客周赛103场F题

解题思路：字符串哈希+字典树+枚举分割点然后二分最大匹配长度

前置知识：字符串哈希、字典树

字符串哈希 学自于董晓老师

字符串哈希的核心思想是将一个字符串映射成一个p进制的数字
Hash函数 $h(s)=\sum_{i=1}^{n}s[i]*p^{n-i}(mod M)$
前缀和 $h[i]=h[i-1]*p+s[i],h[0]=0$
区间和(查询字符串某一区间的哈希值) $h[l,r]=h[r]-h[l-1]*p^{r-l+1}$ ,其中 $p^{r-l+1}$ ，可以用一个 $p$ 数组预先处理出来，这样就可以在后面进行 $O(1)$ 的查询。
时间复杂度 $O(n)$
p通常取 ${131,1331}$ ,M在这里取一个很大的整数 $1ll<<64$ ,然后老师在这里讲到，如果使用了很大的整数 $1ll<<64$ 作为模数，我们并不用去写真正的取模，可以使用无符号长整型 $unsiged \space long \space long$ 来作为 $h$ 数组的数据类型，因为当数据溢出后，它会自己进行取模操作。

#define ull unsigned long long
const int base=131;
//p[i]=base^i,h[i]=s[1~i]的hash值
ull p[s.size()+1],h[s.size()+1];

//预处理hash函数的前缀和
void init()
{
  p[0]=1,h[0]=0;
  for(int i=1;i<=s.size();i++)
  {
    p[i]=p[i-1]*base;
    h[i]=h[i-1]*base+s[i];
  }
}
//计算字符串某一区间的哈希值
ull get(int l,int r)
{
  return h[r]-h[l-1]*p[r-l+1];
}

字典树学自于董晓老师

字典树的本质是一棵26叉树，其重点是需要建立出儿子数组 $ch[N][26]$ 计数数组 $cnt[N]$ ,节点编号 $idx$ ,然后就是实现建树操作和查询操作。其整体的时间复杂度是 $O(n)$ .

建立字典树

儿子数组 $ch[p][j]$ 存储从节点 $p$ 沿着 $j$ 这条边所走到的子节点。 边 $(j)$ 为26个小写字母 $(a~z)$ 对应的映射值 $0-25$ ,所以字典树的每个节点最多可以有26个分叉。

计数数组 $cnt[p]$ 存储以节点p结尾的单词的插入次数。

节点编号 $idx$ 用来给节点进行编号

空trie仅有一个根节点，编号为0.
从根节点开始插入，枚举字符串的每个字符。

如果有儿子，则 $p$ 指针走到儿子，

如果没有儿子，则先创建儿子， $p$ 指针再走到儿子。
在单词结束点记录当前单词的插入次数。

string s;
vector<array<int,26>> tire(total_size+1),cnt(total_size+1);
//total_size表示所有字符串的长度的总和。
int idx=0;
auto insert=[&](string s)->void
{
	int p=0;//从根节点开始插入
    for(int i=0;i<s.size();i++){
    	int j=s[i]-'a';//枚举字符串的每个字符
    	if(!tire[p][j]){
           tire[p][j]=++idx;//如果沿当前字符所指没有儿子，则创建儿子节点
        }
        p=tire[p][j];//如果存在儿子，则p指针更新到当前儿子
    }
    cnt[p]++;//插入后当前字符串的次数增加
};

查询操作

查询操作主要用来查询插入到字典树中的某个字符串的插入次数。

从根节点开始查，扫描字符串
如果存在字母 $s[i]$ ,则走下来，能走到词尾，则返回插入次数。
若没有字母 $s[i]$ ,则直接返回0。

auto query=[&](string s)->int{
  int p=0;//从根节点开始查询。
  for(int i=0;i<s.size();i++)
  {
    	int j=s[i]-'a';//枚举扫描每个字母。
    	if(!tire[p][j]){
          return 0;//如果当前字母不存在，直接返回0。
        }
    	p=tire[p][j];//如果当前字母存在，则继续向下一个字母查询。
  }
  return cnt[p];//如果能够走到词尾，则返回查询字符串的插入次数。
};

本题题解

本题字典树的不同在于 $cnt[]$ 数组，老师讲的 $cnt[]$ 数组记录的每个字符串的插入次数，但由于本题记录的是能够匹配前缀字符串的最大长度和，所以在这里 $cnt[]$ 数组记录的是每个从根节点出发的字符串的次数所以建树的时候需要这样去写

string s;
vector<array<int,26>> tire(total_size+1),cnt(total_size+1);
//total_size表示所有字符串的长度的总和。
int idx=0;
auto insert=[&](string s)->void
{
	int p=0;//从根节点开始插入
    for(int i=0;i<s.size();i++){
    	int j=s[i]-'a';//枚举字符串的每个字符
    	if(!tire[p][j]){
           tire[p][j]=++idx;//如果沿当前字符所指没有儿子，则创建儿子节点		   
        }
         p=tire[p][j];//如果存在儿子，则p指针更新到当前儿子,记录每个子串的出现的次数
         cnt[p]++;//插入后当前字符串的次数增加
    }
};

过题代码

#include <ext/pb_ds/assoc_container.hpp> // 关联式容器基础库
#include <ext/pb_ds/tree_policy.hpp>     // 树结构策略库
#include <bits/stdc++.h>                 // GCC扩展库（推荐竞赛使用）
#define endl '\n'
#define int long long
#define db double
#define i128 __int128_t
#define ull unsigned long long
#define LCHILD(p) (((p) << 1) | 1)
#define RCHILD(p) (((p) + 1) << 1)
#define PI (acos(-1))
using namespace std;
const double EPSILON = 1e-9;
const double pi = asin(1) * 2;
template <class T>
using rbtree = __gnu_pbds::tree<
    /* rbtreet<int> rb;
    // rb.insert(3);  rb.insert(1);  rb.insert(4);  // 插入元素 {1, 3, 4}
    // cout << *rb.find_by_order(1);              // 输出第2小的元素：3
    cout << rb.order_of_key(2);                // 输出比2小的元素数量：1
    */
    T,
    __gnu_pbds::null_type,
    std::less<T>,
    __gnu_pbds::rb_tree_tag,
    __gnu_pbds::tree_order_statistics_node_update>;
// 字符串哈希
void solve()
{
    int base = 131;
    int n, m;
    string s;
    cin >> n >> m >> s;
    s = ' ' + s;
    vector<ull> h(n + 1), p(n + 1);
    h[0] = 0, p[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        p[i] = p[i - 1] * base;
        h[i] = h[i - 1] * base + s[i];
    }
    auto get_substr = [&](int l, int r) -> ull
    {
        return h[r] - h[l - 1] * p[r - l + 1];
    };
    vector<string> a(m + 1);
    int total_sz = 0;
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i];
        total_sz += a[i].size();
    }
    vector<array<int, 26>> tire(total_sz + 1);
    vector<ull> cnt(total_sz + 1);
    int idx = 0;
    auto insert = [&](string &s) -> void
    {
        int p = 0;
        for (auto &c : s)
        {
            int j = c - 'a';
            if (!tire[p][j])
                tire[p][j] = ++idx;
            p = tire[p][j];
            cnt[p]++; 
        }
    };
  //建树
    for (int i = 1; i <= m; i++)
    {
        insert(a[i]);
    }
    map<ull, int> mp;
    auto dfs = [&](auto &&dfs, int p, ull ha, int sum) -> void
    {
        if (p > 0)
        {
            mp[ha] = sum;
        }
        for (int j = 0; j < 26; j++)
        {
            if (!tire[p][j])
                continue;
            int next_p = tire[p][j];
            ull nha = ha * base + (j + 'a');//记录到当前节点的哈希值
            int nsum = sum + cnt[next_p];
            dfs(dfs, next_p, nha, nsum);
        }
    };
    dfs(dfs, 0, 0, 0);
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
      	//枚举分割点，然后从s[i:n-1]二分寻找最大匹配的前缀，然后更新最大值。
        int l = i - 1, r = n + 1;
        while (l + 1 < r)
        {
            int mid = (l + r) / 2;
            if (mp.count(get_substr(i, mid)))
            {
                l = mid;
            }
            else
            {
                r = mid;
            }
        }
        if (mp.count(get_substr(i, l)))
        {
            ans = max(ans, mp[get_substr(i, l)]);
        }
    }
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

#题解分享#