icontofig | 发布于 2019-09-06 22:19:42 | 阅读量 386 | Trie 思维题 hash
发布于 2019-09-06 22:19:42 | Trie 思维题 hash

题目大意

给出一棵trie树和一个字符串,然后对于每一次询问l,r,在Trie树上对子串[l,r]进行匹配。如果在某个字符处失配,则重新跳回Trie树根节点并忽略这个字符继续匹配。

求问对于每一个询问,在匹配过程中会失配几次,且最终会到达哪个节点。

题解

暴力搜索必然是n^2的,对于此题1e5还有多组数据的情况想都不要想。

而每一次失配我们都会重新回到起点。

于是我们可以用预处理从每个位置的下一个位置开始的子串第一次的失配位置是在原字符串中的哪个位置。由于在这个位置我们会失配回到起点然后再次从这个位置的下一个位置开始,所以应该可以想到这个失配过程是完全可以去倍增的!。我们可以用倍增来处理失配次数,然后最终位置可以直接通过一个map存储hash值对应的trie树位置进行查询。

然后考虑如何预处理。

首先我们应该能够想到,如果一个子串能够在trie树中成功匹配,那么它的前缀串也一定能够在trie树中成功匹配。

于是这个性质导致我们可以二分失配的长度,然后我们只需要查询当前二分产生的子串是否能在trie树中进行匹配就可以了。

hash想不被卡的话,感觉就是选一个奇怪点的质数作为base。取模倒是不至于,直接unsigned long long自然溢出就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
typedef unsigned long long ll;
const ll base = 983;
ll h[maxn],bs[maxn];
struct trie{
    int id;
    int ch[26];
}tr[maxn];
int f[maxn][26];
string s;
int x;char c;
int len;
map<ll,int>mp;
int n,m,q,t;
int ql,qr;
void init(){
    bs[0] = 1;
    for(int i = 1;i < maxn;++i){
        bs[i] = bs[i-1] * base;
    }
    return;
}
ll get_hash(int l,int r){
    return h[r] - h[l] * bs[r - l];
}
void dfs(int now,ll hash){
    mp[hash] = now;
    for(int i = 1;i <= 26;++i){
        if(tr[now].ch[i-1] == 0)
            continue;
        dfs(tr[now].ch[i-1],hash * base + i);
    }
    return;
}
int main(){
    init();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--){
        cin >> n >> m >> q;
        for(int i = 0;i <= n;++i){
            for(int j = 0;j < 26;++j)
                tr[i].ch[j] = 0;
        }
        for(int i = 0;i <= m;++i)
            for(int j = 0;j < 26;++j)
                f[i][j] = 0;
        mp.clear();
        for(int i = 1;i <= n;++i){
            cin >> x;cin >> c;
            tr[x].ch[c - 'a'] = i;
        }
        dfs(0,0);
        cin >> s;
        for(int i = m;i >= 1;--i){
            s[i] = s[i-1];
        }
        h[0] = 0;
        for(int i = 1;i <= m;++i){
            h[i] = h[i-1] * base + s[i] - 'a' + 1;
        }
        int log_m = 0;
        while((1<<log_m) <= m){
            log_m++;
        }
        for(int i = 0;i <= m;++i){
            int l = 0,r = m - i;
            int ans = 0;
            while(l <= r){
                int mid = (l + r) >> 1;
                ll p = get_hash(i,i + mid);
                if(!mp.count(p)){
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            f[i][0] = i + l;
        }
        f[m+1][0] = m+1;
        for(int i = 1;i < log_m;++i){
            for(int j = 0;j <= m+1;++j){
                f[j][i] = f[f[j][i-1]][i-1];
            }
        }
        while(q--){
            cin >> ql >> qr;
            ql -= 1;
            int ans = 0;
            for(int i = log_m - 1;i >= 0;--i){
                if(f[ql][i] <= qr){
                    ql = f[ql][i];
                    ans += (1 << i);
                }
            }
            int id = mp[get_hash(ql,qr)];
            cout << ans << " " << id << "\n";
        }
    }
    return 0;
}



内容更新于: 2019-09-06 22:19:42
链接地址: http://blog.leanote.com/post/icontofig/2018-ACM-ICPC-Asia-J

上一篇: The Preliminary Contest for ICPC Asia Xuzhou 2019 I.query 树状数组 二维偏序

下一篇: 2018 ACM/ICPC Xuzhou Regional G.Rikka with Intersections of Paths 树上差分+LCA

386 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航