题解 P5270 无论怎样神树大人都会删库跑路

题意已经说得很清楚了，我们直接开始讲题。

首先考虑一次只插入一个字符。问题只在于我们想要判断最后几个字符是否组成相同，即判断两个可重集合是否相等。这个需求很像字符串哈希的目的（快速判断两个字符串是否相等）。但集合怎么哈希呢？

需求一：判断后缀与 \(S\) 是否相等

一个很简单的思路：像做离散化那样把每个字符映射一个随机的值，然后对集合求和来进行判断。

但是同样很显然的，这个做法存在很大缺陷，比如以下映射关系：

原 1 2 3 4 5
映 7 6 8 5 9

这样集合 2 5 和集合 4 4 4 最后哈希出来都是 \(15\)。

于是我们决定：多做几组映射！然后就做完了。

需求二：一次添加一整个字符串

刚才我们一次只添加了一个字符，但题目要求我们一次添加一整个串。