题意：训练指南P225

分析：二分寻找长度，用hash值来比较长度为L的字串是否相等。

#include 
     
      using namespace std;typedef unsigned long long ull;const int N = 4e4 + 5;const int x = 123;ull H[N], _hash[N], xp[N];int rk[N];char str[N];int m;void get_hash(char *s, int len)  {    H[len] = 0;    for (int i=len-1; i>=0; --i) {        H[i] = H[i+1] * x + (s[i] - 'a');    }    xp[0] = 1;    for (int i=1; i
      
       = m)   pos = max (pos, rk[i]);    }    return pos;}int main(void)  {    while (scanf ("%d", &m) == 1)   {        if (!m) break;        scanf ("%s", &str);        int len = strlen (str);        get_hash (str, len);        if (check (1, len) == -1) puts ("none");        else    {            int l = 1, r = len + 1;            while (r - l > 1)   {                int mid = l + r >> 1;                if (check (mid, len) >= 0)    l = mid;                else    r = mid;            }            printf ("%d %d\n", l, check (l, len));        }    }    return 0;}
      
     

 

后缀数组也可以求解，具体就是二分答案，height数组分组判断是否满足存在题意的解，并使最优。（m=1时特判处理）

#include 
     
       const int N = 4e4 + 5;int sa[N], rank[N], height[N];int ws[N], wa[N], wb[N];char s[N];bool cmp(int *r, int a, int b, int l) {    return (r[a] == r[b] && r[a+l] == r[b+l]);}void DA(char *r, int n, int m = 128) {    int i, j, p, *x = wa, *y = wb;    for (i=0; i
      
       =0; --i) sa[--ws[x[i]]] = i;    for (j=1, p=1; p
       
        = j) y[p++] = sa[i] - j;        for (i=0; i
        
         =0; --i) sa[--ws[x[y[i]]]] = y[i];        std::swap (x, y);        for (p=1, x[sa[0]]=0, i=1; i
         
          = len) {            if (p == -1) {                p = std::max (sa[i-1], sa[i]);            } else {                p = std::max (p, std::max (sa[i-1], sa[i]));            }            cnt++;            if (cnt + 1 >= m) {                ret = std::max (ret, p);            }        } else {            p = -1;            cnt = 0;        }    }    return ret;}int main() {    while (scanf ("%d", &m) == 1) {        if (!m) break;        scanf ("%s", s);        int n = strlen (s);                if (m == 1) {            printf ("%d %d\n", n, 0);            continue;        }                DA (s, n + 1);        calc_height (s, sa, n);                int best = 0, pos = -1;        int left = 0, right = n;        while (left <= right) {            int mid = left + right >> 1;            int res = check (mid, n);            if (res != -1) {                if (best < mid) {                    best = mid;                    pos = res;                } else if (mid > 0 && best == mid && pos < res) {                    pos = res;                }                left = mid + 1;            } else {                right = mid - 1;            }        }        if (pos == -1) {            puts ("none");        } else {            printf ("%d %d\n", best, pos);        }    }     return 0;}