刚学SAM,板题写不对求助 /kel
查看原帖
刚学SAM,板题写不对求助 /kel
61430
Lice楼主2020/5/21 18:40

RT,WA 40pts,rec: https://www.luogu.com.cn/record/33766607

Detail:

  • #2,6,7,8,9: read'1',expected'....'

  • #5: Too short on line 1.

#include <algorithm>
#include <iostream>
#include <map>

using namespace std;
const int L = 1e6 + 5;

namespace SAM {
	const int T = L << 1;
	struct Node {
		map<int, int> ch;
		int link, len;
		int max, min;
	} t[T];
	
	int last;
	int total;
	
	inline void extend(int c) {
		int p = last, np = last = ++total;
		t[np].len = t[p].len + 1;
		
		for (; p && !t[p].ch.count(c); p = t[p].link)
			t[p].ch[c] = np;
		
		if (!p) {
			t[np].link = 1;
		} else {
			int q = t[p].ch[c];
			if (t[q].len == t[p].len + 1) {
				t[np].link = q;
			} else {
				int nq = ++total;
				t[nq].ch = t[q].ch, t[nq].link = t[q].link;
				t[nq].len = t[p].len + 1;
				t[q].link = t[np].link = nq;
				while (p && t[p].ch.count(c) && t[p].ch[c] == q)
					t[p].ch[c] = nq, p = t[p].link;
			}
		}
	}
	
	void init(int* b, int* e) {
		last = total = 1;
		for (register int* p = b + 1; p != e; p++)
			extend(*p - *(p - 1));
		for (register int i = 1; i <= total; i++)
			t[i].min = t[i].len;
	}
	
	int b[T], c[T];
	void topo_sort() {
		for (register int i = 1; i <= total; i++) ++c[t[i].len];
		for (register int i = 1; i <= total; i++) c[i] += c[i - 1];
		for (register int i = 1; i <= total; i++) b[c[t[i].len]--] = i;
	}
	
	void scan(int* b, int* e);
	int get_LCS();
};

void SAM::scan(int* b, int* e) {
	int x = 1, len = 0;
	for (register int* p = b + 1; p != e; p++) {
		int c = *p - *(p - 1);
		for (; x && !t[x].ch.count(c); x = t[x].link, len = t[x].len);
		if (x) ++len, x = t[x].ch[c], t[x].max = max(t[x].max, len);
		else x = 1, len = 0;
	}
	for (register int i = total; i; i--) {
		int x = b[i], f = t[x].link;
		t[f].max = max(t[f].max, t[x].max);
		t[f].max = min(t[f].max, t[f].len);
	}
	for (register int i = 1; i <= total; i++)
		t[i].min = min(t[i].min, t[i].max), t[i].max = 0;
}

int SAM::get_LCS() {
	int ans = 0;
	for (register int i = 1; i <= total; i++)
		ans = max(ans, t[i].min);
	return ans;
}

int dat[L];
signed main() {
	ios::sync_with_stdio(false);
	int n, m;
	
	cin >> n >> m;
	for (register int i = 1; i <= m; i++)
		cin >> dat[i];
	
	SAM::init(dat + 1, dat + 1 + m);
	SAM::topo_sort();
	
	while  (--n) {
		cin >> m;
		for (register int i = 1; i <= m; i++)
			cin >> dat[i];
		if (m == 1) continue;
		SAM::scan(dat + 1, dat + 1 + m);
	}
	
	cout << SAM::get_LCS() + 1 << endl;
	return 0;
}

希望别无意义回复吧。。

2020/5/21 18:40
加载中...