Match

Time Limit:5000MS  Memory Limit:65536K
Total Submit:11 Accepted:7
Case Time Limit:1000MS

Description

PP发明了一种新的串匹配！
给出一个长度为N的整数串A，和一个长度为K（K<=N）的整数串B，A和B中的元素均是不大于S的正整数，我们认为两个串是相等的，当两个串的长 度相当，并且两个串中，对于任意的i，第i个元素在两个串中的排名是一样的。
例如：
1 2 3 5 4
8 10 23 25 24
这两个串是相等的。
现在要求在A的所有长度=B的长度的子串中，有多少子串与B串相等。

Input

第一行三个整数N，K，S。
第二行N个整数表示A串。
第三行K个整数表示B串。

Output

第一行一个P表示A串中一共有多少个子串和B串相等，
接下来P行从小到大每行一个整数，表示和B串相等的A串的子串的第一个元素的位置。

Sample Input

9 6 10
5 6 2 10 10 7 3 2 9
1 4 4 3 2 1

Sample Output

1
3

数据规模：
对于20%的数据N<=10000
对于100%的数据N<=500000，S<=10000

Source

By Mt

这个题目看到之后的第一想法是扩展性的匹配问题。。
那么自然是要改造经典算法了。。
RK算法。。想了一会儿觉得不太靠谱。。
KMP算法。。
KMP算法的使用条件是。。
空串只能等于空串。
两个串相等，那么他们的任意等长前缀也相等。。
这个在此题中是成立的。。
那么我们只需要算出前缀函数。。然后KMP一遍就解决了。。
因为计算前缀函数需要快速知道两个原本相等的字符串，各自+上一个字符之后是否还是相等。。
那么也就是说要有能力计算出一个子序列最后一个字符在这个子序列中的排名。。
这。。。
似乎是划分树的经典应用。。但用划分树是不是太囧了一点？
线段数LogN^2估计会超时。。
那么只好观察一下问题看看有没有神马区间的特殊性质了。。
可以发现需要进行的询问有两种。。一种是在开头处进行。。为A[0…p-1]中有几个数比A[p]小。。扫描一遍就可以了。。
还有一种在KMP过程中的询问。。左右端都是单调递增的。。。
OK了。