学步园

对于数据量比较大字符串处理题来说，字符串哈希完全就是拼rp的问题了，但是有的时候还真是需要运气的。

对于每个后缀的哈希函数H(i)的递推式为：H(i) = H(i + 1) * x + s[i]；那么任意一个起始位置为i长度为L的子串的哈希值H(i, L) = H(i) - H(i + L) * x^L；那么只要预处理H(i)和x^L就可以在常数时间内求出任意子串的哈希值了。具体做法和后缀数组类似，二分答案，每次检查长度为L的子串是否出现了m次以上，由于哈希函数值可以很大，用最原始的数组下标映射肯定是不现实的，其实我们的目的只是判断是否存在m个以上的相同的哈希值，也可以模仿后缀数组的做法，先对所有的哈希值排序，然后分组计算区间的长度。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 40000 + 10;
const int x = 123;
int m, n, pos;
unsigned long long H[maxn], xp[maxn], hash[maxn];
int rank[maxn];
char str[maxn];

int cmp(const int & a, const int & b)
{
    return hash[a] < hash[b] || (hash[a] == hash[b] && a < b);
}

bool possible(int L)
{
    int c = 0;
    pos = -1;
    for(int i = 0; i <= n - L; ++i)
    {
        rank[i] = i;
        hash[i] = H[i] - H[i + L] * xp[L];
    }
    sort(rank, rank + n - L + 1, cmp);
    for(int i = 0; i <= n - L; ++i)
    {
        if(i == 0 || hash[rank[i]] != hash[rank[i - 1]]) c = 0;
        if(++c >= m) pos = max(pos, rank[i]);
    }
    return pos >= 0;
}

int main()
{
    freopen("in.txt", "r",stdin);
    while(~scanf("%d", &m) && m != 0)
    {
        scanf("%s", str); n = strlen(str);
        H[n] = 0; xp[0] = 1;
        for(int i = n - 1; i >= 0; --i) H[i] = (str[i] - 'a') + x * H[i + 1];
        for(int i = 1; i <= n; ++i) xp[i] = xp[i - 1] * x;
        if(!possible(1)) printf("none\n");
        else
        {
            int L = 1, R = n;
            while(R - L > 0)
            {
                int mid = ((L + R) >> 1) + 1;
                if(possible(mid)) L = mid;
                else R = mid - 1;
            }
            possible(L);
            printf("%d %d\n", L, pos);
        }
    }
    return 0;
}

/*
3
baaaababababbababbab
11
baaaababababbababbab
3
cccccc
0

5 12
none
4 2
*/