666E - Forensic Examination - CodeForces Solution

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

#include <queue>
#include <string>

struct Tree {
	static const int N = 5e4;
	
	int tot;
	
	struct node {
		int ls, rs;
		std::pair<int, int> mx;
	} tree[N * 40 + 5];
	
	void pushup(int u) {
		tree[u].mx = std::max(tree[tree[u].ls].mx, tree[tree[u].rs].mx);
	}
	
	void ins(int &u, int L, int R, int x) {
		tree[++tot] = tree[u];
		u = tot;
		if (L == R) {
			tree[u].mx.first = std::max(tree[u].mx.first, 0) + 1;
			tree[u].mx.second = -L;
			return ;
		}
		int mid = (L + R) >> 1;
		if (x <= mid) {
			ins(tree[u].ls, L, mid, x);
		} else {
			ins(tree[u].rs, mid + 1, R, x);
		}
		pushup(u);
	}
	
	int merge(int x, int y, int L, int R) {
		if (!x || !y) {
			return x | y;
		}
		int u = ++tot;
		if (L == R) {
			tree[u].mx.first = tree[x].mx.first + tree[y].mx.first;
			tree[u].mx.second = -L;
			return u;
		}
		int mid = (L + R) >> 1;
		tree[u].ls = merge(tree[x].ls, tree[y].ls, L, mid);
		tree[u].rs = merge(tree[x].rs, tree[y].rs, mid + 1, R);
		pushup(u);
		return u;
	}
	
	std::pair<int, int> ask(int u, int L, int R, int qL, int qR) {
		if (qL > qR || R < qL || L > qR || !u) return {0, -qL};
		if (qL <= L && R <= qR) return tree[u].mx;
		int mid = (L + R) >> 1;
		if (qL <= mid) {
			if (qR <= mid) return ask(tree[u].ls, L, mid, qL, qR);
			return std::max(ask(tree[u].ls, L, mid, qL, qR), ask(tree[u].rs, mid + 1, R, qL, qR));
		} else {
			return ask(tree[u].rs, mid + 1, R, qL, qR);
		}
	}
} TREE;

struct Trie {
	static const int N = 1e6;
	
	int tot;
	
	int trans[N + 5][26];
	
	int insert(int las, int ch) {
		if (trans[las][ch]) {
			return trans[las][ch];
		}
		return trans[las][ch] = ++tot;
	}
	
	void insert(std::string &s) {
		int u = 0;
		for (int i = 0; i < (int)s.size(); i++)
			u = insert(u, s[i] - 'a');
	}
} T;

struct SAM {
	static const int N = 2e6;
	
	int tot;
	
	struct node {
		int len, link, next[26];
	} sam[N + 5];
	
	void init() {
		sam[0].len = 0;
		sam[0].link = -1;
	}
	
	int insert(int las, int ch) {
		int cur = ++tot;
		sam[cur].len = sam[las].len + 1;
		int p = las;
		while (p != -1 && sam[p].next[ch] == 0) {
			sam[p].next[ch] = cur;
			p = sam[p].link;
		}
		if (p == -1) {
			sam[cur].link = 0;
		} else {
			int q = sam[p].next[ch];
			if (sam[q].len == sam[p].len + 1) {
				sam[cur].link = q;
			} else {
				int clone = ++tot;
				sam[clone] = sam[q];
				sam[clone].len = sam[p].len + 1;
				sam[cur].link = clone;
				sam[q].link = clone;
				while (p != -1 && sam[p].next[ch] == q) {
					sam[p].next[ch] = clone;
					p = sam[p].link;
				}
			}
		}
		return cur;
	}
	
	int id[N + 5];
	
	std::pair<int, int> pre[N + 5];
	
	std::vector<int> adj[N + 5];
	
	void add_edge(int u, int v) {
		adj[u].push_back(v);
	}
	
	void build(Trie &T) {
		init();
		std::queue<int> q;
		for (int i = 0; i < 26; i++) {
			if (T.trans[0][i]) {
				int v = T.trans[0][i];
				pre[v] = std::make_pair(0, i);
				q.push(v);
			}
		}
		while (!q.empty()) {
			int u = q.front(); q.pop();
			id[u] = insert(id[pre[u].first], pre[u].second);
			for (int i = 0; i < 26; i++) {
				if (T.trans[u][i]) {
					int v = T.trans[u][i];
					pre[v] = std::make_pair(u, i);
					q.push(v);
				}
			}
		}
		for (int i = 1; i <= tot; i++)
			add_edge(sam[i].link, i);
	}
	
	int dp[N + 5][20];
	
	int Root[N + 5];
	
	void dfs(int u, int fath, int n) {
		dp[u][0] = fath;
		for (int i = 1; i <= 18; i++) {
			if (dp[u][i - 1] == -1) {
				dp[u][i] = -1;
			} else {
				dp[u][i] = dp[dp[u][i - 1]][i - 1];
			}
		}
		for (int v : adj[u]) {
			if (v != fath) {
				dfs(v, u, n);
				Root[u] = TREE.merge(Root[u], Root[v], 1, n);
			}
		}
	}
	
	void insert(std::string s, int id, int n) {
		int u = 0;
		for (int i = 0; i < (int)s.size(); i++) {
			u = sam[u].next[s[i] - 'a'];
			TREE.ins(Root[u], 1, n, id);
		}
	}
} sam;

const int N = 5e5;

int m, q;
std::string s, t[N + 5];

int end[N + 5];

int main() {
	#ifdef LOCAL
//		freopen("data.in", "r", stdin);
//		freopen("data.out", "w", stdout);
	#endif
	
	std::ios::sync_with_stdio(false);
	
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	std::cerr.tie(nullptr);
	
	TREE.tree[0].mx = {-1, 0};
	
	std::cin >> s;
	std::cin >> m;
	for (int i = 1; i <= m; i++)
		std::cin >> t[i];
	T.insert(s);
	for (int i = 1; i <= m; i++)
		T.insert(t[i]);
	sam.build(T);
	for (int i = 1; i <= m; i++)
		sam.insert(t[i], i, m);
	sam.dfs(0, -1, m);
	int u = 0;
	for (int i = 0; i < (int)s.size(); i++)
		end[i] = u = sam.sam[u].next[s[i] - 'a'];
	std::cin >> q;
	while (q--) {
		int l, r, pl, pr;
		std::cin >> l >> r >> pl >> pr;
		int len = pr - pl + 1;
		u = end[pr - 1];
		for (int i = 18; i >= 0; i--) {
			if (sam.dp[u][i] != -1) {
				if (sam.sam[sam.dp[u][i]].len >= len) {
					u = sam.dp[u][i];
				}
			}
		}
		auto ans = TREE.ask(sam.Root[u], 1, m, l, r);
		std::cout << -ans.second << " " << ans.first << "\n";
	}
	
	return 0;
}