NFLS-S20230801

[toc]

F.商品仓库

Description

给出 $P$ 个文本串，有 $Q$ 次询问，每次给定一个模式串 $S$ ，求 $S$ 在多少个文本串中出现。

$1\le P \le 10000,1 \le Q \le 100000$

文本串和模式串的长度均不超过 20

Solution

考虑一个弱化版的问题：求 $S$ 是多少个文本串的前缀 ，可以直接用 trie 树解决。

考虑把原问题转化为弱化版的问题，我们把每个文本串的所有后缀拆出来，然后插到 trie 树里面，同时为了防止同一个文本串对答案重复贡献，除了在 trie 树的节点上面加一个计数器用于统计答案以外，我们还要加一个时间戳，表示上一个更新这个节点的串是哪个串。当这个节点的时间戳不等于当前的串的编号时，我们才更新它。

从代码上来看，是这样的：

void insert(char *s,int T){
	int cur=1;
	int n=strlen(s);
	for(int i=0;i<n;i++){
		if(!ch[cur][s[i]-'a'])ch[cur][s[i]-'a']=++tot;
		cur=ch[cur][s[i]-'a'];
		if(ti[cur]!=T){
			cnt[cur]++;
			ti[cur]=T;
		}
	}
}

其他的判重方法

当然，我们也可以不额外记录 cnt 和 ti 两个信息，转而使用 bitset 记录。

bitset<10010> b[N];   // N represents the number of nodes

void insert(char *s,int T){
    int cur=1;
    int n=strlen(s);
    for(int i=0;i<n;i++){
        if(!ch[cur][s[i]-'a'])ch[cur][s[i]-'a']=++tot;
        cur=ch[cur][s[i]-'a'];
        b[cur][T]=1;
    }
}

Solution-乱搞

乱搞1

我们把每一个文本串的所有子串拆出来，然后塞到一个 map 里面。

但是这种做法只能拿很少的分（悲

乱搞2

更进一步，我们把子串的 hash 塞到 map 里面。（听说有大佬用了神秘的 pbds 容器橄榄了这题 orz）