P3498 [POI2010]KOR-Beads

后缀数组smg？抱歉蒟蒻只会普通Hash

这道题要求选取子串如果反着也被选了的话就不能选,所以很容易想到正反两遍hash.
在这里有很多方式判重，比如lower_bound，链表啊，我在此处使用的是链表.

优化

可以考虑提高代码效率.
比如说如果当前已经分配了的子串加上之后能够得到的最大子串都没有已知的最多子串多，那么就没必要继续做了。
每次只选择可能大于最大值的k去做.
具体实现也不是特别难，可以对比看一下.

参考代码

#include<bits/stdc++.h>
using namespace std;
/*
    正着一遍倒着一遍哈希.
    每次去一个就将两个哈希都存进去.
*/
#define ull unsigned long long
using namespace std;
const int maxn=200005,p=100007;
int n,maxx,cnt,k;
int a[maxn],b[maxn],head[p+5];
ull h1[maxn],h2[maxn],bas[maxn];
struct Kano{
    int nxt;
    ull val;
}kano[maxn];
ull get(int l,int r){
    return min(h1[r]-h1[l-1]*bas[r-l+1],h2[l]-h2[r+1]*bas[r-l+1]);
}
void add(ull x,int y){
    kano[++cnt].val=x;
    kano[cnt].nxt=head[y];
    head[y]=cnt;
}
bool check(ull x){
    int y=x%p;
    for (int i=head[y];i;i=kano[i].nxt){
        if (kano[i].val==x) return 0;
    }
    add(x,y);
    return 1;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) h1[i]=h1[i-1]*p+a[i];
    for(int i=n;i>=1;i--) h2[i]=h2[i+1]*p+a[i];
    bas[0]=1;
    for(int i=1;i<=n;i++)bas[i]=bas[i-1]*p;
    for(int i=1;i<=n;i++){
        if(n/i<maxx) continue;
        int num=0;
        for(int j=1;j<=n;j+=i){
            if(j+i-1>n) break;
            if(num+(n-j+1)/i<maxx) break;//剪枝？
            if(check(get(j,j+i-1))) num++;
        }
        if(num>maxx){
            maxx=num;
            k=1;
            b[k]=i;
        }else if(num==maxx) b[++k]=i;
    }
    printf("%d %d\n",maxx,k);
    for (int i=1;i<=k;i++)
    printf("%d ",b[i]);
    return 0;
}

P3498 [POI2010]KOR-Beads

原文：https://www.cnblogs.com/Fast-Bird/p/11972823.html