程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LA 4513 Stammering Aliens 字符串hash

LA 4513 Stammering Aliens 字符串hash

編輯：C++入門知識

字符串hash模板，

本題是求，給定字符串s中至少出現m次的最長字符串長度，及此時起始位置的最大值

LA 4513 Stammering Aliens

白書p225

//#pragma warning (disable: 4786)
//#pragma comment (linker, "/STACK:16777216")
//HEAD
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
//LOOP
#define FE(i, a, b) for(int i = (a); i <= (b); ++i)
#define FD(i, b, a) for(int i = (b); i>= (a); --i)
#define REP(i, N) for(int i = 0; i < (N); ++i)
#define CLR(A,value) memset(A,value,sizeof(A))
#define CPY(a, b) memcpy(a, b, sizeof(a))
#define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
//INPUT
#define RI(n) scanf("%d", &n)
#define RII(n, m) scanf("%d%d", &n, &m)
#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)
#define RS(s) scanf("%s", s)
//OUTPUT
#define WI(n) printf("%d\n", n)
#define WS(s) printf("%s\n", s)

const int INF = 0x3f3f3f3f;

#define ULL unsigned long long

const int maxn = 40010;
const int SEED = 13331;
int n, m;
int rank[maxn];
char s[maxn];

ULL xp[maxn];
ULL hashs[maxn];
int pos;

ULL ha[maxn];
int cmp(const int &a, const int &b)///cmp注意
{
    return ha[a] < ha[b] || (ha[a] == ha[b] && a < b);
}
int possible(int L)
{
    for (int i = 0; i < n - L + 1; i++)
    {
        rank[i] = i;
        ///
        ha[i] = hashs[i] - hashs[i + L] * xp[L];
    }
    sort(rank, rank + n - L + 1, cmp);
    int x;
    pos = -1;
    for (int i = 0; i < n - L + 1; i++)
    {
        if (i == 0 || ha[rank[i]] != ha[rank[i - 1]]) x = 0;
        if (++x >= m) pos = max(pos, rank[i]);
    }
    return pos >= 0;
}


int main()
{
    ///
    xp[0] = 1;
    for (int i = 1; i < maxn; i++)
        xp[i] = xp[i - 1] * SEED;

    while (cin >> m && m)
    {
        RS(s);
        n = strlen(s);

        ///
        hashs[n] = 0;
        for (int i = n - 1; i >= 0; i--)
            hashs[i] = hashs[i + 1] * SEED + s[i];

        if (!possible(1)) puts("none");
        else
        {
            int L = 1, R = n;
            while (L <= R)
            {
                int M = (L + R) >> 1;
                if (possible(M)) L = M + 1;
                else R = M - 1;
            }
            possible(R);
            printf("%d %d\n", R, pos);
        }

    }
    return 0;
}