[洛谷P1420]最长连号

题目大意：输入$n$个正整数，（$1\leq n\leq 10000$),要求输出最长的连号的长度。（连号指从小到大连续自然数）

题解：考虑从小到大连续自然数差分为$1$，所以可以把原数列差分（后缀自动机不怎么会写啊），查询串为$1,11,111,\dots,111\dots(n-1个1)$，把它们插入到$AC$自动机中，然后查询即可，原数列差分不为$0,1$时赋为$0$（因为不对答案有影响）

卡点：1.原序列差分的数不为$0,1$时会挂。。。

C++ Code：（$AC$自动机2018-8-13）

#include <cstdio>

#include <queue>

#define maxn 10010

using namespace std;

int n;

int s[maxn], a[maxn], b[maxn];

int nxt[maxn][2], fail[maxn], cnt[maxn], tot;

int root = 0;

queue<int> q;

void add(int *s, int n) {

	int now = root, len = n;

	for (int i = 1; i <= len; i++) {

		if (nxt[now][s[i]]) now = nxt[now][s[i]];

		else now = nxt[now][s[i]] = ++tot;

		cnt[now]++;

	}

}

void build() {

	for (int i = 0; i < 2; i++)

		if (nxt[root][i]) fail[nxt[root][i]] = root, q.push(nxt[root][i]);

	while (!q.empty()) {

		int x = q.front(); q.pop();

		for (int i = 0; i < 2; i++) {

			if (nxt[x][i]) fail[nxt[x][i]] = nxt[fail[x]][i], q.push(nxt[x][i]);

			else nxt[x][i] = nxt[fail[x]][i];

		}

	}

}

int ask(int *s, int n) {

	int now = root, ans = 0, len = n;

	for (int i = 1; i <= n; i++) {

		if (s[i] > 1 || s[i] < 0) s[i] = 0;

		now = nxt[now][s[i]];

		for (int j = now; j && ~cnt[j]; j = fail[j]) ans += cnt[j], cnt[j] = -1;

	}

	return ans;

}

int main() {

	scanf("%d", &n);

	for (int i = 1; i <= n; i++) scanf("%d", &s[i]), b[i] = 1;

	for (int i = 2; i <= n; i++) a[i - 1] = s[i] - s[i - 1];

	add(b, n - 1);

	build();

	printf("%d\n", ask(a, n - 1) + 1);

	return 0;

}

　　

题解：当然我们也可以用后缀自动机来做，对差分串建一个后缀自动机，发现若答案长度为$len$，那么长度为$len-1$也是答案，所以可以二分答案（如果你直接求最长的$1$的字段也可以，但我就得这样不是很优美有趣）。

卡点：无

C++ Code：

#include <cstdio>

#include <cstring>

#define maxn 20010

using namespace std;

int nxt[maxn][2], fail[maxn], R[maxn], idx;

int last, now, np, p, t, root;

int n, a[maxn];

void insert(int x) {

    if (x < 0 || x > 1) x = 0;

    R[now = ++idx] = R[p = last] + 1; last = now;

    for (; ~p && !nxt[p][x]; p = fail[p]) nxt[p][x] = now;

    if (!~p) {fail[now] = root; return ;}

    if (R[t = nxt[p][x]] == R[p] + 1) {fail[now] = t; return ;}

    R[np = ++idx] = R[p] + 1;

    for (int i = 0; i < 2; i++) nxt[np][i] = nxt[t][i];

    fail[np] = fail[t]; fail[t] = fail[now] = np;

    for (; nxt[p][x] == t; p = fail[p]) nxt[p][x] = np;

}

int tmp[maxn];

bool check(int mid) {

    for (int i = 1; i <= mid; i++) tmp[i] = 1;

    int now = root;

    for (int i = 1; i <= mid; i++) {

		now = nxt[now][tmp[i]];

		if (!now) return false;

	}

	return true;

}

int main() {

    scanf("%d", &n);

    fail[root = 0] = -1; idx = last = 1;

    scanf("%d", &a[1]);

    for (int i = 2; i <= n; i++) {

        scanf("%d", &a[i]);

        insert(a[i] - a[i - 1]);

    }

    int l = 0, r = n, ans = 0;

    while (l <= r) {

        int mid = l + r >> 1;

        if (check(mid)) {

            l = mid + 1;

            ans = mid;

        } else r = mid - 1;

    }

    printf("%d\n", ans + 1);

}