一个字符串的前缀是指包含该字符第一个字母的连续子串，例如：abcd的所有前缀为a, ab, abc, abcd。
给出一个字符串S，求其所有前缀中，字符长度与出现次数的乘积的最大值。
例如：S = “abababa” 所有的前缀如下:

“a”, 长度与出现次数的乘积 1 * 4 = 4,
“ab”,长度与出现次数的乘积 2 * 3 = 6,
“aba”, 长度与出现次数的乘积 3 * 3 = 9,
“abab”, 长度与出现次数的乘积 4 * 2 = 8,
“ababa”, 长度与出现次数的乘积 5 * 2 = 10,
“ababab”, 长度与出现次数的乘积 6 * 1 = 6,
“abababa”, 长度与出现次数的乘积 7 * 1 = 7.

其中"ababa"出现了2次，二者的乘积为10，是所有前缀中最大的。
输入
输入字符串S, (1 <= L <= 100000， L为字符串的长度)，S中的所有字符均为小写英文字母。
输出
输出所有前缀中字符长度与出现次数的乘积的最大值。
输入样例
abababa
输出样例
10

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int sa[maxn], rak[maxn];
int tx[maxn], height[maxn];
char s[maxn];
int n, m, p;
int cnt[maxn];
struct node {
	int x, y, id;
}a[maxn], b[maxn];

void rsort() {
	for (int i = 1; i <= m; i++) tx[i] = 0;
	for (int i = 1; i <= n; i++) tx[a[i].y]++;
	for (int i = 1; i <= m; i++) tx[i] += tx[i - 1];
	for (int i = 1; i <= n; i++) b[tx[a[i].y]--] = a[i];
	for (int i = 1; i <= m; i++) tx[i] = 0;
	for (int i = 1; i <= n; i++) tx[b[i].x]++;
	for (int i = 1; i <= m; i++) tx[i] += tx[i - 1];
	for (int i = n; i >= 1; i--) a[tx[b[i].x]--] = b[i];
}

void ssort() {
	rsort();
	p = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i].x != a[i - 1].x || a[i].y != a[i - 1].y) ++p;
		rak[a[i].id] = p;
	}
	for (int i = 1; i <= n; i++) {
		a[i].x = rak[i];
		a[i].id = sa[rak[i]] = i;
		a[i].y = 0;
	}
	m = p;
}

void solve() {
	m = 127;
	for (int i = 1; i <= n; i++) {
		a[i].x = a[i].y = s[i];
		a[i].id = i;
	}
	ssort();
	for (int j = 1; j <= n; j <<= 1) {
		for (int i = 1; i + j <= n; i++) {
			a[i].y = a[i + j].x;
		}
		ssort();
		if (p == n) break;
	}
}


void get_Height() {
	int k = 0;
	for (int i = 1; i <= n; i++) {
		if (k) k--;
		int j = sa[rak[i] - 1];
		while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;
		height[rak[i]] = k;
	}
}

int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	solve(); get_Height(); 
	int mm = 1e8;
	for (int i = rak[1] + 1; i <= n; i++) {
		mm = min(mm, height[i]);
		cnt[mm]++;
	}
	mm = 1e8;
	for (int i = rak[1]; i >= 1; i--) {
		mm = min(mm, height[i]);
		cnt[mm]++;
	}
	for (int i = n; i >= 1; i--) {
		cnt[i] += cnt[i + 1];
	}
	long long ans = 0;
	for (int i = 1; i <= n; i++) {
		ans = max(ans, 1LL * i * (cnt[i] + 1));
	}
	printf("%lld\n", ans);
	return 0;
}