BZOJ1461字符串的匹配

题目
具体思路与KMP板子很像;
大致思路是将两个数字的排名来当字符比较
用树状数组 \(log_2(n)\) 的复杂度来找排名。
一定要注意边界问题
具体实现思路可以看代码
(PS:有奆佬说这题很板子，也许是我太弱了叭QAQ)

//9:30  开始写题，有些思路
//  40  思路被pass，不会写了
//  55  决定去看kmp板子及思想找思路 
//      其主要思想是当出现字符串不匹配的情况时，
//	    可以知道一部分之前已经匹配的的文本内容，
//      利用这些信息避免从头再去做匹配，而其中前缀表担负重任。 
//      也许有用？？？ 
//10:50 什么思路依然没有，感觉不会，要寄
//11:30 看题解吧，寄寄寄
//15:30 看了题解也学不会呜呜呜┭┮﹏┭┮
//16:20 蛙趣，终于整明白这道题了
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std;

int n, m, s;
int a[5211314 >> 3], b[5211314 >> 3], bit[5211314 >> 3];
int rank1[5211314 >> 3], rank2[5211314 >> 3], nex[5211314 >> 3];
int ans[5211314 >> 2], tot;

struct BinaryIndexedTree {
	inline int lowbit(int x) {
		return (x & (-x));
	}
	inline void Add(int x, int val) {
		while (x <= s) {
			bit[x] += val;
			x += lowbit(x); 
		}
		return;
	}
	inline int Query(int x) {
		int ans = 0;
		while (x > 0) {
			ans += bit[x];
			x -= lowbit(x);
		}
		return ans;
	}
}tree;

inline bool compared(int x, int y) {
	if (tree.Query(y) == rank1[x] && tree.Query(y - 1) == rank2[x]) {
		return true;
	}
	else {
		return false;
	}
}

int main() {
	cin >> n >> m >> s;
	for (int i = 1; i <= n; ++ i) cin >> a[i];
	for (int i = 1; i <= m; ++ i) {
		cin >> b[i];
		tree.Add(b[i], 1);
		rank1[i] = tree.Query(b[i]);
		rank2[i] = tree.Query(b[i] - 1);
		//将b数组的排名保存
	}
	memset(bit, 0, sizeof(bit));
	nex[0] = 1;
	for (int i = 2, j = 0; i <= m; ++ i) {
		tree.Add(b[i], 1);
		while (j > 0 && !compared(j + 1, b[i])) {
			for (int k = i - j; k < i - nex[j]; ++ k) {
				//注意，此时j没有加1。则i-j到i-nex[j] - 1为以j为下标的数组向右移动的长度
				//可以自己手模一下
				//因为下一个不能将nex[j]的点减去，所以
				tree.Add(b[k], -1);
			}
			j = nex[j];
		}
		if (compared(j + 1, b[i]) == true) j ++;
		//这里可以抽象的理解为每次b[j+1]与b[j]的排名名次的差和b[i]与b[i-1]的排名名次的差一样
		//也可以抽象的理解为每次加在的排名区间一样
		//(如在数组1,2,5后插入4中树状数组的bit[4]和bit[3] 
		// 与在数组1,2,10后插入5中的树状数组bit[5]与bit[4]的值一样)
		nex[i] = j;
	}//处理出来自己的nex
	memset(bit, 0, sizeof(bit));
	for (int i = 1, j = 0; i <= n; ++ i) {
		tree.Add(a[i], 1);
		while (j > 0 && !compared(j + 1, a[i])) {
			for (int k = i - j; k < i - nex[j]; ++ k) {
				tree.Add(a[k], -1);
			}
			j = nex[j];
		}
		if (compared(j + 1, a[i])) j ++;
		if (j == m) {
			ans[++ tot] = i - m + 1;
			for (int q = i - j + 1; q <= i - nex[j]; ++ q) {
				//此时j已经加1，所以这里i - j + 1到i - nex[j]为以j为下标的数组移动的长度
				//可以自己手模一下
				tree.Add(a[q], -1);
			}
			j = nex[j];
		}
	}
	cout << tot << endl;
	for (int i = 1; i <= tot; ++ i) {
		cout << ans[i] << endl;
	}
	return 0;
}