[CEOI2011] Matching

定义两个长度相同的串 $a,b$ 是同构的，当且仅当对于任意 $i,j$，$a_i<a_j\iff b_i<b_j$。

求短串在长串中的所有同构匹配。

不难想到使用 KMP。那么我们还需要对于每个前缀在指针跳的时候快速判断两个 border 同时各添加一个数后是否仍然同构。一种想法是使用树状数组查询区间内小于 $k$ 的数的个数，时间复杂度 $O(n\log n)$。

更加聪明的做法是用链表 $O(n)$ 预处理每个位置在以它为结尾的前缀中的前驱和后继的位置，两个同构串后各添加一个数后仍然同构，当且仅当该数大于另一个串中添加数在另一个串中的前驱对应到自己串中的位置上的数，小于另一个串中添加数在另一个串中的后继对应到自己串中的位置上的数。