PAT (Top Level) Practice1005 Programming Pattern （35 分）

题目链接：https://pintia.cn/problem-sets/994805148990160896/problems/994805154748940288

用后缀数组求出长度为n所有子字符串的大小关系，然后得出重复最多的。

算法：后缀数组

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<set>
#define maxn 1100000
using namespace std;
int n;
int sa[maxn], ranks[maxn];
int height[maxn];
int t1[maxn], t2[maxn];
int c[maxn];
string s;
int m;
bool cmp(int *r, int a, int b, int l) {
	return r[a] == r[b] && r[a + l] == r[b + l];
}
void da(int t) {
	int p;
    m = s.length();
	
	int *x = t1, *y = t2;
	for (int i = 0; i < t; i++) {
		c[i] = 0;
	}
	for (int i = 0; i < m; i++) {
		c[x[i] = s[i]]++;
	}
	for (int i = 1; i < t; i++) {
		c[i] += c[i - 1];
	}
	for (int i = m - 1; i >= 0; i--) {
		sa[--c[x[i]]] = i;
	}
	for (int k = 1; k <= m;) {
		p = 0;
		for (int i = m - k; i < m; i++) {
			y[p++] = i;
		}
		for (int i = 0; i < m; i++) {
			if (sa[i] >= k) {
				y[p++] = sa[i] - k;
			}
		}
		for (int i = 0; i < t; i++) {
			c[i] = 0;
		}
		for (int i = 0; i < m; i++) {
			c[x[y[i]]]++;
		}
		for (int i = 1; i < t; i++) {
			c[i] += c[i - 1];
		}
		for (int i = m - 1; i >= 0; i--)
			sa[--c[x[y[i]]]] = y[i];
		swap(x, y);
		p = 1;
		x[sa[0]] = 0;
		for (int i = 1; i < m; i++) {
			x[sa[i]] = cmp(y, sa[i - 1], sa[i], k) ? p - 1 : p++;
		}
		if (p >= m)
			break;
		t = p;
		k = k << 1;
		if (k >= n)
		{
			for (int i = 0; i < m; i++) {
				ranks[sa[i]] = i;
			}
			break;
		}
	}
}
void getheight() {
	int k = 0;
	for (int i = 0; i < m; height[ranks[i++]] = k) {
		if (k)--k;
		if (ranks[i] == 0) {
			height[ranks[i]] = 0;
			continue;
		}
		for (int j = sa[ranks[i] - 1]; s[i + k] == s[j + k];) {
			k++;
			if (k >= n) {
				k = n; break;                              
			}
		}
	}
}
int main() {
	cin >> n;
	cin.get();
	getline(cin, s);
	da(128);
	getheight();
	int h = sa[0], _h = -1;
	int ans = 1, ans1 = 1;
	for (int i = 1; i < m; i++) {
		if (height[i] >= n) {
			ans++;
		}
		else {
			if (ans > ans1||(_h==-1)||(ans==ans1&&s[h]<s[_h])) {
				ans1 = ans;
				_h = h;
			}
			ans = 1, h = sa[i];
		}
	}
	if (ans > ans1 || (ans == ans1 && s[h] < s[_h])) {
		ans1 = ans; _h = h;
	}
	cout << s.substr(_h, n) << \" \" << ans1 << endl;
	return 0;
}