AC自动机（查询）

        上面讲了AC自动机是如何建树和建自动机的，这里要讲的是AC自动机的查询和各个数组的功能和作用。

        其实AC自动机的查询和KMP算法是及其相近的，都是一个指针跑主串，另一个指针跑ne串（这里就是回跳边）。

        话都说到这了，不妨先来看看ne的真实用处吧。上次有提过，ne数组存的其实就是最长的后缀模式串，当我们找到一个字串在主串中匹配的时候，我们并不能直接继续下去，因为如果两个单词之间存在借位的情况，我们就会忽略从而导致错误，所以我们需要记录下当前字母先前能回跳的位置，这样我们才能将我们所要的字串一网打尽，和KMP其实是完全相同的。

        那么转移边呢，我们说过我们要用一个指针去遍历树，但是我们遍历树的时候一但到头了怎么办，是不是要沿着原路反回。现在我们用一个转移边就可以节省这一部分的操作，那么为什么要把转移边建在自己回跳边的儿子上呢？其实是为了契合上面所建的回跳边，这样我们的跑主串的指针就一定会是不回退的，只需要回跳边不断操作，主串完全就是一个匹配版，不需要进行复杂的操作。

        代码如下：

int query(char *s)
{
	int ans = 0;
	
	for(int k = 0, i = 0; s[k]; k ++)
	{
		i = s[k] - 'a';
		
		for(int j = i; j && ~cnt[j]; j = ne[j])
		{
			ans += cnt[j];
			cnt[j] = -1;
		}
	}
	
	return ans;
}

        这里需要注意，我们的计数的维护，当我们找到某一个字串后，我们会加上它在Trie树中存储的个数，同时别忘了清零，否则会多加，这里用的是位运算的小技巧。 

        贴一道例题：

https://www.luogu.com.cn/problem/P3808https://www.luogu.com.cn/problem/P3808 

题目描述

给定