LINK：All with Pairs
那天下午打这个东西的时候状态极差 推这个东西都推了1个多小时 (比赛是中午考试的我很困 没睡觉直接开肝果然不爽
一开始看错匹配的位置了 以为是\(1-l\)和\(r-(r-l+1)\)进行匹配。
我想这不是随便写个trie树？？？码完发现过不去样例 我真的是眼瞎
后来看清了。
大致思路如下 可以直接暴力枚举\(n^2\)个点对 找到最大的匹配位置这个也可以暴力 由于串长总和是M。
这一部分复杂度也不过是\(n^2+M\)的。
过不了 就可以思考能不能从大到小枚举匹配长度 看有多少对符合。
发现这样也非常难做。
不过可以对单个串枚举匹配长度 然后看有多少个串可以进行匹配。
这样容易想到字符串hash 来进行快速的匹配 开C++11 直接unodered_map...
然后可以发现这样做 会带来重复 仔细观察对于同一个串的重复位置 可以发现这是一个KMP的nex数组的问题。
然后每次统计到一个位置就把自己的nex数组的那个位置给减掉即可。