用一组数据测试了一下所有的 AC 提交,只有我自己的和黑泽明的没有被叉。
测试地址
数据本身挂在附件里了。
原因是他们需要枚举每一个连通块并且在每个连通块里都对字符串跑匹配,复杂度就退化成了 O(nm∑∣T∣)O(nm \sum|T|)O(nm∑∣T∣)。
正确的复杂度应当是 O(nm∣Σ∣q+∑∣T∣)O(nm|\Sigma|q+\sum|T|)O(nm∣Σ∣q+∑∣T∣) ,这组数据可以稳定通过。
所以为什么这个数据这么弱啊