WHU1564---Circle (后缀数组)

Description
Here is a circle sequence S of length n, and you can choose a position and remove the number on it.
After that,you will get a integer. More formally,you choose a number x( 1<=x<=n ),then you will get the integer Rx = Sx+1……SnS1S2….. Sx-1.
The problem is which number x you choose will get the k-th smallest Rx.
If there are more than one answer,choose the one with the smallest x.
Input
First line of each case contains two numbers n and k.(2?≤?k≤??n?≤?1?000?000).

Next line contains a number of length n. Each position corresponds to a number of 1-9.
Output
Output x on a single line for each case.
Sample Input
10 5
6228814462
10 4
9282777691
Sample Output
6
7
Hint
Source

先把串重复一次,求出后缀数组,重复是为了能得到循环串的字典序,然后对于位置在前一半的后缀,可以把循环串看成它的一个前缀,当然字典序完全没影响,然后其实每一个Rx都是去掉这个后缀的第一个字符,所以如果这个后缀的rank是k的话,这个后缀的其中一个前缀就是Rx,那么去掉的那个字符的位置就是sa[k] - 1了,当然是循环串,所以如果k==1的话,去掉的是最后一个字符

/*************************************************************************
    > File Name: A.cpp
    > Author: ALex
    > Mail: [email protected] 
    > Created Time: 2015年04月19日 星期日 17时07分42秒
 ************************************************************************/

#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <map>
#include <bitset>
#include <set>
#include <vector>

using namespace std;

const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair <int, int> PLL;

class SuffixArray
{
    public:
        static const int N = 2002000;
        int init[N];
        int X[N];
        int Y[N];
        int Rank[N];
        int sa[N];
        int height[N];
        int buc[N];
        int LOG[N];
        int dp[N][20];
        int size;

        void clear()
        {
            size = 0;
        }

        void insert(int n)
        {
            init[size++] = n;
        }

        bool cmp(int *r, int a, int b, int l)
        {
            return (r[a] == r[b] && r[a + l] == r[b + l]);
        }

        void getsa(int m) //m一般为最大值+1
        {
            init[size] = 0;
            int l, p, *x = X, *y = Y, n = size + 1;
            for (int i = 0; i < m; ++i)
            {
                buc[i] = 0;
            }
            for (int i = 0; i < n; ++i)
            {
                ++buc[x[i] = init[i]];
            }
            for (int i = 1; i < m; ++i)
            {
                buc[i] += buc[i - 1];
            }
            for (int i = n - 1; i >= 0; --i)
            {
                sa[--buc[x[i]]] = i;
            }
            for (l = 1, p = 1; l <= n && p < n; m = p, l *= 2)
            {
                p = 0;
                for (int i = n - l; i < n; ++i)
                {
                    y[p++] = i;
                }
                for (int i = 0; i < n; ++i)
                {
                    if (sa[i] >= l)
                    {
                        y[p++] = sa[i] - l;
                    }
                }
                for (int i = 0; i < m; ++i)
                {
                    buc[i] = 0;
                }
                for (int i = 0; i < n; ++i)
                {
                    ++buc[x[y[i]]];
                }
                for (int i = 1; i < m; ++i)
                {
                    buc[i] += buc[i - 1];
                }
                for (int i = n - 1; i >= 0; --i)
                {
                    sa[--buc[x[y[i]]]] = y[i];
                }
                int i;

                for (swap(x, y), x[sa[0]] = 0, p = 1, i = 1; i < n; ++i)
                { 
                    x[sa[i]] = cmp(y, sa[i - 1], sa[i], l) ? p - 1 : p++; 
                }
            }
        }

        void getheight()
        {
            int h = 0, n = size;
            for (int i = 0; i <= n; ++i)
            {
                Rank[sa[i]] = i;
            }
            height[0] = 0;
            for (int i = 0; i < n; ++i)
            {
                if (h > 0)
                {
                    --h;
                }
                int j =sa[Rank[i] - 1];
                for (; i + h < n && j + h < n && init[i + h] == init[j + h]; ++h);
                height[Rank[i] - 1] = h;
            }
        }   

        //预处理每一个数字的对数，用于rmq，常数优化
        void initLOG()
        {
            LOG[0] = -1;
            for (int i = 1; i < N; ++i)
            {
                LOG[i] = (i & (i - 1)) ? LOG[i - 1] : LOG[i - 1] + 1;
            }
        }

        void initRMQ()
        {
            initLOG();
            int n = size;
            int limit;
            for (int i = 0; i < n; ++i)
            {
                dp[i][0] = height[i];
            }
            for (int j = 1; j <= LOG[n]; ++j)
            {
                limit = (n - (1 << j));
                for (int i = 0; i <= limit; ++i)
                {
                    dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
                }
            }
        }

        int LCP(int a, int b)
        {
            int t;
            a = Rank[a];
            b = Rank[b];
            if (a > b)
            {
                swap(a, b);
            }
            --b;
            t = LOG[b - a + 1];
            return min(dp[a][t], dp[b - (1 << t) + 1][t]);
        }

        void solve(int k)
        {
            int cnt = 0;
            for (int i = 1; i <= size; ++i)
            {
                if (sa[i] < size / 2)
                {
                    ++cnt;
                    if (cnt == k)
                    {
                        if (sa[i] == 0)
                        {
                            printf("%d\n", (size >> 1));
                        }
                        else
                        {
                            printf("%d\n", sa[i]);
                        }
                        break;
                    }
                }
            }
        }
}SA;

char str[1001000];

int main()
{
    int n, k;
    while (~scanf("%d%d", &n, &k))
    {
        scanf("%s", str);
        SA.clear();
        for (int i = 0; i < n; ++i)
        {
            SA.insert(str[i] - ‘0‘);
        }
        for (int i = 0; i < n; ++i)
        {
            SA.insert(str[i] - ‘0‘);
        }
        SA.getsa(13);
        SA.getheight();
        SA.solve(k);
    }
    return 0;
}