题目概述

给一个字符串 $S$ ，选一个子串 $T$ ，使 ${T\over T-Border(T)}$ 最大。

解题报告

每个串的Border并不好考虑，但是可以考虑枚举Border，然后去找子串。

假设长度为 $len$ 的Border以 $a$ 和 $b$ 两个位置结尾，那么可以算出答案为 $len+b-a\over b-a$ ，由于要求最大值，因此在最大的情况下，$a$ 和 $b$ 两个位置组成的串的Border一定是 $len$ 这个串（即 $len$ 最大的前缀等于后缀），所以正确性没有问题。

现在的问题就是枚举Border，考虑枚举SAM的一个节点，$pos$ 集合一致，因此肯定取最长的串以及最接近的 $a$ 和 $b$ ，用线段树合并来维护 $pos$ 集合，同时求出最小的 $b-a$ 即可。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200000,maxm=maxn<<1,maxt=1e7,maxi=26;

int n,ansU,ansD;char s[maxn+5];
int E,lnk[maxm+5],nxt[maxm+5],to[maxm+5];
int ro[maxm+5],pl,ls[maxt+5],rs[maxt+5],MIN[maxt+5],L[maxt+5],R[maxt+5],si[maxt+5];
struct SAM{
    int pl,ro,son[maxm+5][maxi],fai[maxm+5],MAX[maxm+5],ID[maxm+5];
    inline int newnode() {pl++;return pl;}
    SAM() {pl=0;ro=newnode();}
    int Extend(int p,int c,int i){
        int np=newnode();MAX[np]=MAX[p]+1;ID[np]=i;
        while (p && !son[p][c]) son[p][c]=np,p=fai[p];
        if (!p) {fai[np]=ro;return np;}
        int q=son[p][c];if (MAX[p]+1==MAX[q]) {fai[np]=q;return np;}
        int nq=newnode();MAX[nq]=MAX[p]+1;
        for (int i=0;i<maxi;i++) son[nq][i]=son[q][i];
        fai[nq]=fai[q];fai[q]=fai[np]=nq;
        while (p && son[p][c]==q) son[p][c]=nq,p=fai[p];
        return np;
    }
}SAM;

inline void Add(int x,int y) {to[++E]=y;nxt[E]=lnk[x];lnk[x]=E;}
inline int newnode() {pl++;return pl;}
void Pushup(int p){
    si[p]=si[ls[p]]+si[rs[p]];
    MIN[p]=min(ls[p]?MIN[ls[p]]:1e9,rs[p]?MIN[rs[p]]:1e9);
    if (!ls[p] || !rs[p]) L[p]=L[ls[p]+rs[p]],R[p]=R[ls[p]+rs[p]]; else {
        MIN[p]=min(MIN[p],L[rs[p]]-R[ls[p]]);
        L[p]=L[ls[p]];R[p]=R[rs[p]];
    }
    if (si[p]==2) MIN[p]=min(MIN[p],R[p]-L[p]);
}
void Insert(int &p,int pos,int l=1,int r=n){
    if (!p) p=newnode();
    if (l==r) {si[p]++;L[p]=R[p]=l;MIN[p]=1e9;return;}
    int mid=l+(r-l>>1);
    pos<=mid?Insert(ls[p],pos,l,mid):Insert(rs[p],pos,mid+1,r);
    Pushup(p);
}
void Merge(int &x,int y){
    if (!y) return;if (!x) {x=y;return;}
    Merge(ls[x],ls[y]);Merge(rs[x],rs[y]);
    Pushup(x);
}
void Fix(int x,int y) {if ((LL)x*ansD>(LL)ansU*y) ansU=x,ansD=y;}
void DFS(int x){
    if (SAM.ID[x]) Insert(ro[x],SAM.ID[x]);
    for (int j=lnk[x];j;j=nxt[j]){
        DFS(to[j]);
        Merge(ro[x],ro[to[j]]);
    }
    if (MIN[ro[x]]<1e9) Fix(SAM.MAX[x],MIN[ro[x]]);
}
int gcd(int a,int b) {return b?gcd(b,a%b):a;}
int main(){
    scanf("%s",s+1);n=strlen(s+1);
    for (int i=1,p=SAM.ro;i<=n;i++) p=SAM.Extend(p,s[i]-'a',i);
    for (int i=2;i<=SAM.pl;i++) if (SAM.fai[i]) Add(SAM.fai[i],i);
    ansU=0;ansD=1;
    DFS(SAM.ro);
    ansU+=ansD;
    int r=gcd(ansU,ansD);
    printf("%d/%d\n",ansU/r,ansD/r);
    return 0;
}