C++11(clang++ 3.9) 解法, 执行用时: 647ms, 内存消耗: 3300K, 提交时间: 2020-04-26 20:45:37

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

const ull base = 123;
const int maxn = 1e5 + 7;
ull ha[2][maxn], po[maxn];
char s[maxn];
int n;
ull getha(int l, int r, ull *h){
    return h[r] - po[r - l + 1] * h[l - 1];
}

int lcp(int i, int j, ull *h){
    int l = 1, r = n - j + 1, mid;
    while(l <= r){
        mid = (l + r) >> 1;
        if(getha(i, i + mid - 1, h) == getha(j, j + mid - 1, h)) l = mid + 1;
        else r = mid - 1;
    }
    return l - 1;
}
int main(){
    int T;
    scanf("%d", &T);
    po[0] = 1;
    for(int i = 1; i < maxn; ++i) po[i] = po[i - 1] * base;
    while(T--){
        scanf("%s", s + 1);
        n = strlen(s + 1);
        for(int i = 1; i <= n; ++i){
            ha[0][i] = ha[0][i - 1] * base + s[i] - 'a';
        }
        for(int i = n; i >= 1; --i){
            ha[1][n - i + 1] = ha[1][n - i] * base + s[i] - 'a';
        }
        int ans = 1;
        for(int len = 1; len <= n; ++len){
            for(int i = len; i + len <= n; i += len){
                int j = i + len;
                if(s[i] != s[j]) continue;
                int rpart = lcp(i, j, ha[0]);
                int lpart = lcp(n - j + 1, n - i + 1, ha[1]);
                int res = lpart + rpart + len - 1;
               // printf("len %d l %d r %d\n", len, lpart, rpart);
                ans = max(ans, res / len);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 789ms, 内存消耗: 2912K, 提交时间: 2020-04-27 13:29:06

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef unsigned long long LL;
using namespace std;

const int base = 233;

int t, len;
LL l[100005], r[100005], p[100005];
char s[100005];

LL check(int l, int r, LL *a){
	return a[r] - a[l - 1] * p[r - l + 1];
}

int get(int x, int y, LL *p){
	int l = 1, r = len - y + 1, ans = 1;
	while(l <= r){
		int mid = (l + r) >> 1;
		if(check(x, x + mid - 1, p) == check(y, y + mid - 1, p)) ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	return ans;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &t);
	p[0] = 1;
	for (int i = 1; i <= 100000; i++) p[i] = p[i - 1] * base;
	while(t--){
		scanf("%s", s + 1);
		len = strlen(s + 1);
		l[0] = r[0] = 0;
		int ans = 1;
		for (int i = 1; i <= len; i++) l[i] = l[i - 1] * base + s[i] - 'a';
		for (int i = len; i >= 1; i--) r[len - i + 1] = r[len - i] * base + s[i] - 'a';
		for (int sz = 1; sz <= len; sz++){
			for (int i = sz; i + sz <= len; i += sz){
				int j = i + sz;
				if(s[i] != s[j]) continue;
				int szl = get(len - j + 1, len - i + 1, r);
				int szr = get(i, j, l);
				int sum = szl + szr + sz - 1;
				ans = max(ans, sum / sz);
			}
		}
		printf("%d\n", ans);
	}

	return 0;
}
/**/