1. 题目描述
给定一个长为$n \in [1, 4000]$的字符串，求其中长度最长的子串，并且该子串在原串中出现至少$m$次，并求最右起始位置。
2. 基本思路
两种方法：二分+后缀数组，或者二分+哈希。
（1） 二分+后缀数组
对子串长度进行二分，若不同后缀的公共前缀超过这个值，则对计数值累加。若计数值超过m，则证明这个公共前缀是有效的，计数过程中同时维护pos（最右边界），从而更新rpos。
（2）二分+哈希
仍然是对长度进行二分，然后枚举其实位置计算该长度的子串的哈希值，排序后，计算，超过m表示是有效的子串，从而更新最右位置。哈希采用LCP哈希。
3. 代码
（1）后缀数组
/* 4080 */
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 const int maxn = ;
char s[maxn];
int a[maxn];
int height[maxn], sa[maxn], rrank[maxn];
int wa[maxn], wb[maxn], wc[maxn], wv[maxn];
int rpos, 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 *r, int *sa, int n, int m) {
int i, j, *x=wa, *y=wb, *t, p; for (i=; i<m; ++i) wc[i] = ;
for (i=; i<n; ++i) wc[x[i]=r[i]]++;
for (i=; i<m; ++i) wc[i] += wc[i-];
for (i=n-; i>=; --i) sa[--wc[x[i]]] = i;
for (j=,p=; p<n; j*=, m=p) {
for (p=, i=n-j; i<n; ++i) y[p++] = i;
for (i=; i<n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
for (i=; i<n; ++i) wv[i] = x[y[i]];
for (i=; i<m; ++i) wc[i] = ;
for (i=; i<n; ++i) wc[wv[i]]++;
for (i=; i<m; ++i) wc[i] += wc[i-];
for (i=n-; i>=; --i) sa[--wc[wv[i]]] = y[i];
for (t=x,x=y,y=t,x[sa[]]=,p=,i=; i<n; ++i)
x[sa[i]] = cmp(y, sa[i-], sa[i], j) ? p- : p++;
}
} void calheight(int *r, int *sa, int n) {
int i, j, k = ; for (i=; i<=n; ++i) rrank[sa[i]] = i;
for (i=; i<n; height[rrank[i++]]=k)
for (k?k--:, j=sa[rrank[i]-]; r[j+k]==r[i+k]; ++k) ;
} void printSa(int n) {
for (int i=; i<=n; ++i)
printf("%d ", sa[i]);
putchar('\n');
} void printHeight(int n) {
for (int i=; i<=n; ++i)
printf("%d ", height[i]);
putchar('\n');
} bool judge(int bound, int n) {
int cnt = , pos = -; rpos = -;
rep(i, , n+) {
if (height[i] >= bound) {
pos = max(pos, sa[i]);
++cnt;
} else {
if (cnt >= m)
rpos = max(pos, rpos);
pos = sa[i];
cnt = ;
}
}
if (cnt >= m)
rpos = max(pos, rpos); return rpos!=-;
} void solve() {
int n; for (int i=; ; ++i) {
if (s[i] == '\0') {
n = i;
break;
}
a[i] = s[i] - 'a' + ;
}
a[n] = ;
if (m == ) {
printf("%d 0\n", n);
return ;
} da(a, sa, n+, );
calheight(a, sa, n); int l = , r = n, mid;
int ans = , ansp; while (l <= r) {
mid = (l + r) >> ;
if (judge(mid, n)) {
ans = mid;
ansp = rpos;
l = mid + ;
} else {
r = mid - ;
}
} if (ans)
printf("%d %d\n", ans, ansp);
else
puts("none");
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif while (scanf("%d", &m)!=EOF && m) {
scanf("%s", s);
solve();
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}
（2）哈希
/* 4080 */
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 #define ULL unsigned __int64 const int MOD = ;
const int maxn = ;
ULL H[maxn], base[maxn];
ULL Hash[maxn];
int pos[maxn];
char s[maxn];
int c[];
int m, len;
int rp; void init() {
base[] = ;
rep(i, , maxn)
base[i] = base[i-] * MOD;
} bool comp(const int& a, const int& b) {
if (Hash[a] == Hash[b])
return a<b;
return Hash[a] < Hash[b];
} bool judge(int l) {
int n = len - l + ;
for (int i=; i<n; ++i) {
pos[i] = i;
Hash[i] = H[i] - H[i+l] * base[l];
} sort(pos, pos+n, comp); int i = ;
rp = -;
while (i < n) {
int j = i++;
while (i<n && Hash[pos[i]]==Hash[pos[j]])
++i;
if (i-j >= m)
rp = max(rp, pos[i-]);
} return rp >= ;
} void solve() {
len = strlen(s) ; memset(c, , sizeof(c));
rep(i, , len)
++c[s[i]-'a'];
H[len] = ;
per(i, , len)
H[i] = H[i+] * MOD + s[i]-'a'; bool flag = false; rep(i, , ) {
if (c[i] >= m) {
flag = true;
break;
}
} if (!flag) {
puts("none");
return ;
} int ans = , ansp = -;
int l = , r = len, mid; while (l <= r) {
mid = (l + r) >> ;
if (judge(mid)) {
ans = mid;
ansp = rp;
l = mid + ;
} else {
r = mid - ;
}
} printf("%d %d\n", ans, ansp);
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif init();
while (scanf("%d", &m)!=EOF && m) {
scanf("%s", s);
solve();
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}