Tag-hash

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2019-09-06 22:19:42 |  0 Comments  |  Trie 思维题 hash

2018 ACM/ICPC Asia Jiaozuo Regional K.Counting Failures on a Trie 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
 2017-01-08 11:52:59 |  0 Comments  |  hash DP

【BZOJ3507【CQOI】通配符匹配DP+Hash

题目描述

几乎所有操作系统的命令行界面(CLI)中都支持文件名的通配符匹配以方便用户。最常见的通配符有两个,一个是星号(“*”),可以匹配0个及以上的任意字符:另一个是问号(“?”),可以匹配恰好一个任意字符。
现在需要你编写一个程序,对于给定的文件名列表和一个包含通配符的字符串,判断哪些文件可以被匹配。

输入格式

第一行是一个由小写字母和上述通配符组成的字符串。
第二行包含一个整数n,表示文件个数。
接下来n行,每行为一个仅包含小写字母字符串,表示文件名列表。

输出格式

输出n行,每行为“YES”或“NO”,表示对应文件能否被通配符匹配。

样例输入

*aca?ctc
6
acaacatctc
acatctc
aacacatctc
aggggcaacacctc
aggggcaacatctc
aggggcaacctct

样例输出

YES
YES
YES
YES
YES
NO

数据范围及提示

对于100%的数据

·字符串长度不超过1 00000

· 1 <=n<=100

·通配符个数不超过10

题解

DP+Hash(刚学Hash)
f[i][j]表示第i个通配符能否匹配到第j个位置。
因为一个*会把字符串分成两段,所以这个*分开的两边一定是要求一样的,这里可以利用hash判断。
然后我们就可以得到通配符串被*分成好几段,这样就可以得到转移。
枚举起点,如果可以匹配就可以转移。
有一些比较方便的处理,比如S最后加一个?,以及s最后加任意一个字符
这样的时间复杂度封顶大概是O(N*k*len),所以一开始自己想到了但是没敢写,但是发现这个转移其实时间复杂度是不满的,所以可以AC
%%%DaD3zZ

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
const int maxn = 100010;
const int base = 131;
char S[maxn],s[maxn];
ull hash[2][maxn],bin[maxn];
int p[20],t,n;
bool f[12][maxn];
inline void hash_table(char str[
Title - Artist
0:00