P8451 [LSOT-1] Crosspain

enucai · 2022-07-27 16:04:41 · 题解

Preface

做法0：我不会数据结构！

期望得分：100。

真的想骂骂这个数据啊。

Analysis

乱搞选手，复杂度不正确，可惜出题人没有卡。

算法：字符串 hash。

首先想用一个容器记录一下每次询问后的字符串集。每个字符串记录其长度与 hash 值。

对于操作 1，直接计算字符串 s 的 hash 值，并将其加入容器。

对于操作 2，则直接遍历容器中的元素，并枚举 s 的起始位置，用字符串 hash 的前缀和快速算出这一个子串的 hash 值。若相等，则答案 +1。

注意容器的选择，应用 multiset 而不是 set。但是直接用 set 会 MLE，因此选择在使用 set 的同时记录一下这种串的个数即可。

最坏时间复杂度 O(q^2)，莫名其妙就过了。

Code

#include<bits/stdc++.h>
using namespace std;
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define Rof(i,j,k) for(int i=(j);i>=(k);i--)
#define mkp make_pair
#define fi first
#define se second
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ull unsigned long long
#define int long long
const ull B=13331;
set<pair<pair<ull,int>,int>> S[500010];
ull sum[1000010],mi[1000010];
int q;
char s[1000010];
signed main(){IOS;
    mi[0]=1;
    For(i,1,1000000) mi[i]=mi[i-1]*B;
    cin>>q; S[0].clear();
    For(_,1,q){
        int op,__; cin>>op>>__>>(s+1);
        int m=strlen(s+1);
        S[_]=S[__];
        if(op==1){
            ull now=0ull;
            For(i,1,m) now=now*B+(ull)(s[i]-'a');
            auto tmp=S[_].lower_bound(mkp(mkp(now,m),0));
            if(tmp->fi==mkp(now,m)){
                int cnt=tmp->se;
                S[_].erase(tmp),S[_].emplace(mkp(now,m),cnt+1);
            }else{
                S[_].emplace(mkp(now,m),1);
            }
        }else{
            sum[0]=0ull;
            For(i,1,m) sum[i]=sum[i-1]*B+(ull)(s[i]-'a');
            int res=0;
            for(auto[hl,cnt]:S[_]){
                For(i,1,m-hl.se+1) if(sum[i+hl.se-1]-sum[i-1]*mi[hl.se]==hl.fi) res+=cnt;
            }
            cout<<res<<"\n";
        }
    }
}