2014 ACM/ICPC 牡丹江 J Jacobi Pattern
程序员文章站
2022-03-15 20:45:51
...
题意:
给出一个串(),求出所有满足要求的偶数长度区间的个数:前面一半与后面一半是循环同构。
题解:
稍微有点面向数据。。。因为无法构造出能卡掉这种做法的数据。。。
一个串的前半与后半是循环同构,即,即这个串拥有一个等于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;
}
上一篇: Win11右键上下文菜单存在BUG 微软将着手进行修复
下一篇: 4.散列的定义和整数散列