C++14(g++5.4) 解法, 执行用时: 171ms, 内存消耗: 66028K, 提交时间: 2019-08-10 11:34:20

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
struct PAM
{
	int s[N], nex[N][26], fail[N], len[N], cnt[N], num[N];
	int length,last,idx;
	int id[N];/*出现位置*/
	void newnode(int l)
	{
		len[idx] = l;
		memset(nex[idx], 0, sizeof(nex[idx]));
	}
	void init()
	{
		idx = 1, last = 0;
		len[0] = 0, len[1] = -1;
		cnt[1] = cnt[0] = 0;
		num[0] = num[1] = 0;
		memset(nex[0], 0, sizeof(nex[0]));
		memset(nex[1], 0, sizeof(nex[1]));
		length = 0;
		s[length] = -1;
		fail[0] = 1;
	}
	int get_fail(int x)
	{
		while (s[length - len[x] - 1] != s[length])
			x = fail[x];
		return x;
	}
	void insert(int c)
	{
		s[++length] = c;
		int p = get_fail(last);
		if (!nex[p][c])
		{
			++idx;
			newnode(len[p] + 2);
			id[idx] = length - len[idx] + 1;
			fail[idx] = nex[get_fail(fail[p])][c];
			nex[p][c] = idx;
			num[idx] = num[fail[idx]] + 1;
		}
		last = nex[p][c];
		cnt[last]++;
	}
}pam;
char s1[N], s2[N];
bool vis[N];
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		int n;
		string s;
		s = " ";
		scanf("%d", &n);
		scanf("%s %s", s1, s2);
		pam.init();
		for (int i = 0; i < n; i++)
			pam.insert(s1[i] - 'a'), s += s1[i];
		pam.length = 0, pam.s[0] = -1;
		int mx = 0;
		memset(vis, 0, sizeof(vis));
		vis[0] = vis[1] = true;
		int now = 0;
		vector<int> a, b;
		for (int i = 0; i < n; i++)
		{
			pam.s[++pam.length] = s2[i] - 'a';
			while (now != 1 && (!pam.nex[now][s2[i] - 'a'] || pam.s[pam.length - pam.len[now] - 1] != pam.s[pam.length]))
				now = pam.fail[now];
			if (pam.nex[now][s2[i] - 'a'])
			{
				int id = pam.nex[now][s2[i] - 'a'];
				if (pam.len[id] > mx)
				{
					mx = pam.len[id];
					vis[id] = 1;
					a.clear();
					a.push_back(pam.id[id]);
					b.clear();
					b.push_back(i - mx + 2);
				}
				else if (pam.len[id] == mx && !vis[id])
				{
					vis[id] = 1;
					a.push_back(pam.id[id]);
					b.push_back(i - mx + 2);
				}
				now = pam.nex[now][s2[i] - 'a'];
			}
			else
				now = 0;
		}
		if (mx == 0)
		{
			printf("0\n");
			continue;
		}
		string tep;
		int ans = 0;
		tep = s.substr(a[0], mx);
		for (int i = 1; i < a.size(); i++)
		{
			string t = s.substr(a[i],mx);
			if (tep > t)
			{
				tep = t;
				ans = i;
			}
		}
		printf("%d\n", mx);
		printf("%d %d\n",a[ans], a[ans]+mx-1);
		printf("%d %d\n", b[ans], b[ans] + mx - 1);
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 204ms, 内存消耗: 135160K, 提交时间: 2020-08-27 21:30:07

#include <cstdio>
#define MN 1001000
#define base 83
#define mod 998244853

int nxt[MN][30], len[MN], Min[MN], fail[MN];
int n, tot = 1;
int ansl, ansr;
int bl, br;
bool vis[MN];
char A[MN], B[MN];
long long p[MN], mi[MN];

void init() {
	mi[0] = 1;
	for(int i = 1; i <= n; i++) p[i] = (p[i - 1] * base + A[i] - 'a' + 1) % mod;
	for(int i = 1; i <= n; i++) mi[i] = mi[i - 1] * base % mod;
}

int get(int l, int r) {
	return (p[r] - p[l - 1] * mi[r - l + 1] % mod + mod) % mod;
}

int LCP(int l, int a, int len) {
	int L = 0, R = len + 1;
	while(L < R) {
		int mid = L + R >> 1;
		if(get(l, l + mid - 1) == get(a, a + mid - 1)) L = mid + 1;
		else R = mid;
	}
	return L - 1;
}

bool rw(int l, int r) {
	int len1 = r - l + 1, len2 = ansr - ansl + 1;
	if(len1 > len2) {
		ansl = l;
		ansr = r;
		return 1;
	}
	if(len1 < len2) return 0;
	int len = LCP(l, ansl, len1);
	if(len == len1 + 1) return 0;
	if(A[l + len] < A[ansl + len]) {
		ansl = l;
		ansr = r;
		return 1;
	}
	return 0;
}

void build(char *s, int type) {
	int now = 0;
	for(int i = 1; i <= n; i++) {
		while(s[i] != s[i - len[now] - 1]) now = fail[now];
		if(!nxt[now][s[i] - 'a']) {
			nxt[now][s[i] - 'a'] = ++tot;
			int cur = nxt[now][s[i] - 'a'];
			len[cur] = len[now] + 2;
			now = fail[now];
			while(s[i] != s[i - len[now] - 1]) now = fail[now];
			fail[cur] = nxt[now][s[i] - 'a'];
			if(fail[cur] == cur) fail[cur] = 1;
			now = cur;
			if(type) Min[now] = i - len[now] + 1;
		} else now = nxt[now][s[i] - 'a'];
		if(Min[now] && !type && !vis[now]) {
			if(rw(Min[now], Min[now] + len[now] - 1)) bl = i - len[now] + 1, br = i;
			vis[now] = 1;
		}
	}
}

int main() {
	int T;
	scanf("%d", &T);
	while(T--) {
		for(int i = 0; i <= tot; i++) {
			Min[i] = len[i] = fail[i] = vis[i] = 0;
			for(int j = 0; j < 26; j++) nxt[i][j] = 0;
		}
		fail[1] = 0;
		len[0] = -1;
		len[1] = 0;
		tot = 1;
		ansl = 0;
		ansr = -1;
		scanf("%d%s%s", &n, A + 1, B + 1);
		init();
		build(A, 1);
		build(B, 0);
		if(ansr == -1) puts("0");
		else printf("%d\n%d %d\n%d %d\n", br - bl + 1, ansl, ansr, bl, br);
	}
	return 0;
}