欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2014 ACM/ICPC 牡丹江 J Jacobi Pattern

程序员文章站 2022-03-15 20:45:51
...

题意:


给出一个串(len<5000len<5000),求出所有满足要求的偶数长度区间[l,r][l,r]的个数:前面一半与后面一半是循环同构。

题解:


稍微有点面向数据。。。因为无法构造出能卡掉这种做法的数据。。。

一个串的前半与后半是循环同构,即S=UV,T=VU,ST=UVVUS = UV , T = VU,ST = UVVU,即这个串拥有一个等于U的border,且中间剩下的左半右半相等。

于是对于原串的每一个后缀,做一次KMP,求出border,注意这里用到的border是小于等于区间长度的一半,只需要在求KMP的时候加以限制即可。

然后对于每个长度为偶数的区间,check每一个border是否满足要求。

由于限制区间长度为偶数,且一个串的两边循环同构本身自带剪枝。

因此。。。附带一个小常数。。。

Code:

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
const int maxn = 5000+100;
int a[maxn];
int n,m;
ULL Seed_Pool[]={911,146527,19260817,91815541};
ULL Mod_Pool[]={29123,998244353,1000000009,4294967291ull};
ULL bas[maxn];
ULL Seed = Seed_Pool[2];
ULL Mod = Mod_Pool[3];
struct Hash_1D{
    ULL sum[maxn];
    void init(int seedIndex,int modIndex){
        for (int i=1;i<=n;i++){
            sum[i] = (sum[i-1]*Seed%Mod+a[i])%Mod;
        }
    }
    ULL getHash(int l,int r){
        return (sum[r]-sum[l-1]*bas[r-l+1]%Mod+Mod)%Mod;
    }
}hasher;
struct KMP{
    int nxt[maxn];
    void init(int st){
        nxt[st+1] = 0;
        for (int i=2+st;i<=n;i++){
            nxt[i] = nxt[i-1];
            while (nxt[i] && a[i] != a[st+nxt[i]+1] )nxt[i] = nxt[st+nxt[i]];
            nxt[i] += (a[i] == a[st+nxt[i]+1] && nxt[i] *2 +2 <= i-st);
        }
    }
}kmper;
vector<vector<int>> ans(maxn);
int main(){
    bas[0]=1;
    for (int i=1;i<maxn;i++){
        bas[i] = bas[i-1]*Seed%Mod;
    }
    int T;
    scanf("%d",&T);
    while (T--){
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++){
            scanf("%d",a+i);
        }
        for (int i=0;i<=n;i++)ans[i].clear();
        hasher.init(2,3);
        int tot =0;
        for (int i=0;i<n;i++){
            kmper.init(i);
            for (int j=1+i;j<=n;j++){
                int len = j-i;
                if (len %2 )continue;
                for (int tmp = kmper.nxt[j];tmp;tmp = kmper.nxt[i+tmp]){
                    if (tmp *2 >len)continue;
                    if (tmp*2 == len){
                        ans[len].push_back(i+1);
                        tot ++;
                        break;
                    }
                    int l = i+1 + tmp;
                    int r = i+1 + len/2-1;
                    ULL hashl = hasher.getHash(l,r);
                    int ll = r+1;
                    int rr = ll + r-l;
                    ULL hashr = hasher.getHash(ll,rr);
                    if (hashl == hashr){
                        ans[len].push_back(i+1);
                        tot ++;
                        break;
                    }
                }
            }
        }
        int tot2 = 0;
        for (int i=0;i<=n;i++){
            if (ans[i].empty())continue;
            tot2 ++;
        }
        printf("%d %d\n",tot,tot2);
        for (int i=0;i<=n;i++){
            if (ans[i].empty())continue;
            printf("%d %d ",i,(int)ans[i].size());
            for (int j=0;j<ans[i].size();j++){
               printf("%d%c",ans[i][j],j+1 == ans[i].size()?'\n':' ');
            }

        }
    }
    return 0;
}


相关标签: String