POJ 1743 Musical Theme Hash + 二分

原本是《后缀数组——处理字符串的有力工具》论文中的第一道例题，发现自己智商不够，一个下午没有看懂后缀数组= =，就用hash写了

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;
typedef long long LL;
const int maxn = 20000 + 5;
const int mod = 65536;
const int phc = 1e9 + 7;
int num[maxn], val[maxn], n;
int head[mod], nxt[maxn], pos[maxn], sz;
LL hval[maxn];
LL hc[maxn], pw[maxn];

bool ok(int k) {
	memset(head, -1, sizeof(head));
	sz = 0;
	for (int i = k; i <= n; i++) {
		LL nowval = hc[i] - hc[i - k] * pw[k], nowpos = nowval & (mod - 1);
		for (int j = head[nowpos]; ~j; j = nxt[j]) {
			if (nowval == hval[j] && i - pos[j] >= k) {
				return true;
			}
		}
		pos[sz] = i; hval[sz] = nowval;
		nxt[sz] = head[nowpos]; head[nowpos] = sz++;
	}
	return false;
}

int main() {
	pw[0] = 1;
	for (int i = 1; i < maxn; i++) {
		pw[i] = pw[i - 1] * phc;
	}
	while (scanf("%d", &n), n) {
		for (int i = 1; i <= n; i++) scanf("%d", &num[i]);
		for (int i = 1; i < n; i++) val[i] = num[i + 1] - num[i] + 100;
		n--;
		hc[0] = 0;
		for (int i = 1; i <= n; i++) {
			hc[i] = hc[i - 1] * phc + val[i];
		}
		int l = 1, r = n, ans = 0;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (ok(mid)) {
				l = mid + 1; ans = mid + 1;
			}
			else r = mid - 1;
		}
		if (ans < 5) ans = 0;
		printf("%d
", ans);
	}
}