题解

· · 题解

先说个题外话，这道题哈希用 29，会 WA 几个点！？？？（2023.6.24）

upd：原因是写代码的时候没发现字符串访问了未赋值的地方导致哈希出了问题……有点内个了 o(╥﹏╥)o，哈希用 29 也是可以的（2023.10.17）

题意

已知 N 个长度不超过 30 的字符串 S_i，有 Q 次询问，每次询问给出一个长度依旧不超过 30 的字符串 T_i，求出 T_i 在 S_i 中第一次出现的位置 w_i（没有则为 N）加上 i=1\sim w 的 S_i 与 T_i 的最长公共前缀的长度之和。

题目分析

首先一看内存限制，好家伙，32 MB，字典树建不下，这可怎么办？但我们可以发现，我们可以将询问离线下来，分开求 w_i 和最长公共前缀的长度之和。

求 w_i 是比较简单的，直接 hash+unordered_map 就行了，接着我们考虑求最长公共前缀的长度之和，由于这道题的字符串长度并不是非常大，我们可以将 S_i 和 T_i 的每个前缀单独拎出来然后求哈希值，再用 unordered_map 统计与 T_i 的前缀的哈希值、长度均相同的 S_i 的前缀的个数之和，而这即为最长公共前缀的长度之和，具体细节可以康康代码。

时间复杂度是优秀的 O(N\times |S|)，空间复杂度也是 O(N\times |S|)。

Code

#include <bits/stdc++.h>
#define uLL unsigned long long
using namespace std;
const int N = 3e4+5;
const uLL base = 31;
int n, q, ans[N];
uLL az[N], bb[N];
unordered_map <uLL, int> vis;
char s[N][35], t[N][35];
vector <int> to[N];

template <typename T> void read(T& x) {
    x = 0; int f = 0; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c=getchar();
    while(c >= '0' && c <= '9') x=(x<<1)+(x<<3)+(c^48), c=getchar();
    x=(f ? -x : x);
}
int lne; char put[105];
template <typename T> void write(T x, char ch) {
    lne = 0; if(x < 0) putchar('-'), x=-x;
    do { put[++lne]=x%10, x/=10; } while(x);
    while(lne) putchar(put[lne--]^48);
    putchar(ch);
}

signed main() {
    read(n);
    for(int i = 1; i <= n; ++i) {
        scanf("%s", s[i]+1);
        int ln = strlen(s[i]+1);
        for(int len = 1; len <= ln; ++len)
            az[i]=az[i]*base+s[i][len]-'a'+1;
        if(vis.find(az[i]) == vis.end())
            vis[az[i]]=i;//先统计第一个哈希值为这个的S_i的位置 
    }
    read(q);
    for(int i = 1; i <= q; ++i) {
        scanf("%s", t[i]+1);
        int ln = strlen(t[i]+1);
        for(int o = 1; o <= ln; ++o)
            bb[i]=bb[i]*base+t[i][o]-'a'+1;
        if(vis.find(bb[i]) == vis.end())//找w_i,找不到就是n 
            to[n+1].push_back(i), ans[i]+=n;
        else
            to[vis[bb[i]]].push_back(i), ans[i]+=vis[bb[i]];
    }
    for(int i = 1; i <= n; ++i) 
        az[i]=0;
    for(int i = 1; i <= q; ++i) 
        bb[i]=0;
    for(int len = 1; len <= 30; ++len) {
        vis.clear();
        for(int i = 1; i <= q; ++i) 
            if(strlen(t[i]+1) >= len) //upd:!!!就是这个地方!!!一定要判 
                bb[i]=bb[i]*base+t[i][len]-'a'+1;//更新哈希值 
        for(int i = 1; i <= n; ++i) {
            if(strlen(s[i]+1) < len) continue;//长度小的不算 
            az[i]=az[i]*base+s[i][len]-'a'+1;
            ++vis[az[i]];//统计个数 
            for(int j : to[i]) //找到w_i等于i的T_i贡献答案 
                if(vis.find(bb[j]) != vis.end())
                    ans[j]+=vis[bb[j]];//贡献答案 
        }
        for(int j : to[n+1])//特殊处理找不到w_i的T_i 
            if(vis.find(bb[j]) != vis.end())
                ans[j]+=vis[bb[j]];
    }
    for(int i = 1; i <= q; ++i) 
        write(ans[i], '\n');
    return 0;
}