jzoj3962 [NOI2015模拟12.27] str

Solution

---

更正，si=slen(s)−i−1$s_i=s_{len(s)-i-1}$

Solution

---

比赛的时候成功水到预期中的60分，不知道该不该高兴

最容易想到的应该是O(n^3)暴力枚举子串判断是否回文，可以正反hash一下就O(n^2)了
正解可以考虑建一个回文自动机，节点数就是第一问答案。然鹅我不太会写
也可以manacher找出所有的回文子串记录下来，用hash判重得到第一问答案，这里打双hash会比较优秀

对于第二问我们知道排序的时间复杂度取决于数组的大小和比较元素的复杂度、交换元素的复杂度。可以只扔进去编号这样交换就是O(1)的了。剩下比较两个字符串的大小可以二分一个前缀并O(1)判断是否相等，这样找到的第一位不同就能判断惹

据说还有后缀数组的做法，可以学习一波
找模数的时候惊奇地发现20020303是素数55566677也是素数，这么好记不如记下来

Code

---

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)

typedef long long LL;
typedef std:: pair <int,int> pair;
typedef std:: pair <LL,LL> Lpair;
const LL MOD1=1000000007;
const LL MOD2=55566677;
const LL BASE1=233;
const LL BASE2=109;
const int N=200005;

int rad[N],n,k,cnt;
char str[N],a[N];
LL hash1[N],hash2[N],pow1[N],pow2[N],m;

std:: map <Lpair,bool> map;
std:: vector <pair> vec;

Lpair get_hash(int x,int y) {
    LL h1=(hash1[y]-hash1[x-1]*(LL)pow1[y-x+1]%MOD1+MOD1)%MOD1;
    LL h2=(hash2[y]-hash2[x-1]*(LL)pow2[y-x+1]%MOD2+MOD2)%MOD2;
    return Lpair(h1,h2);
}

void solve1() {
    rep(i,0,n-1) {
        a[i*2]='#';
        a[i*2+1]=str[i];
    }
    a[n*2]='#';
    int len=n*2+1,mx=0,pos=0;
    int ans=0;
    rep(i,0,len-1) {
        if (i<mx) {
            rad[i]=std:: min(mx-i,rad[pos*2-i]);
        } else rad[i]=0;
        while ((i-rad[i]>0)&&(i+rad[i]+1<len)&&(a[i-rad[i]-1]==a[i+rad[i]+1])) {
            rad[i]++;
            Lpair h=get_hash((i-rad[i])/2+1,(i+rad[i]-1)/2+1);
            if ((!rad[i]&&a[i]=='#')||map.count(h)) continue;
            map[h]=1; ans++; vec.push_back(pair((i-rad[i])/2,(i+rad[i]-1)/2));
        }
        if (i+rad[i]>mx) {
            mx=i+rad[i];
            pos=i;
        }
    }
    printf("%d\n", ans); k=m%ans+1;
}

bool cmp(pair a,pair b) {
    int lena=a.second-a.first+1;
    int lenb=b.second-b.first+1;
    if (lena!=lenb) return lena<lenb;
    int l=1,r=lena,rec=0;
    while (l<=r) {
        int mid=(l+r)>>1;
        Lpair ha=get_hash(a.first+1,a.first+mid);
        Lpair hb=get_hash(b.first+1,b.first+mid);
        if (ha==hb) l=mid+1;
        else r=mid-1;
    }
    return (str[a.first+r]<str[b.first+r]);
}

void solve2() {
    std:: sort(vec.begin(),vec.end(),cmp);
    rep(i,vec[k-1].first,vec[k-1].second) putchar(str[i]);
    putchar('\n');
}

void init() {
    scanf("%d%lld",&n,&m);
    scanf("%s",str);
    pow1[0]=pow2[0]=1;
    rep(i,1,n) {
        hash1[i]=((LL)hash1[i-1]*(LL)BASE1+str[i-1])%MOD1;
        hash2[i]=((LL)hash2[i-1]*(LL)BASE2+str[i-1])%MOD2;
        pow1[i]=(LL)pow1[i-1]*(LL)BASE1%MOD1;
        pow2[i]=(LL)pow2[i-1]*(LL)BASE2%MOD2;
    }
}

int main(void) {
    init();
    solve1();
    solve2();
    return 0;
}