登录
← 返回首页 | 代码片段 › 6 字符串 › 6.5 最小表示法 › 最小表示法 / 搜索
JSON MD

6.5 最小表示法

Necklace 最小表示法判断同构
27 行
CPP JSON
【Necklace(最小表示法判断同构)】 最小表示法模板,求字符串循环同构的最小字典序表示。 核心函数: int sakura(char a[]) — 后缀数组 int judge(char a[],char b[]) — 判定函数
C++ 26 行 CPP
#include<cstring>
#include<cstdio>
int i,j,k,n,m,x,y,st;char a[2000003],b[2000003];
inline int sakura(char a[]){
    i=1,j=2;
    while(i<=n&&j<=n){
        k=0;
        while(k<n&&a[i+k]==a[j+k])++k;
        if(k==n)break;
        if(a[i+k]>a[j+k]){i+=k+1;if(i==j)++i;}
        else{j+=k+1;if(i==j)++j;}
    }
    return i<j?i:j;
}
inline int judge(char a[],char b[]){
    n=strlen(a+1);
    for(i=1;i<=n;++i)a[i+n]=a[i],b[i+n]=b[i];
    x=sakura(a),y=sakura(b);
    a[x+n]=b[y+n]='\0';
    return !strcmp(a+x,b+y);
}
int main(){
    scanf("%s%s",a+1,b+1);
    if(judge(a,b)){printf("Yes\n");puts(a+x);}
    else printf("No");
}
Snowflake Snow Snowflakes 最小表示法+Hash
44 行
CPP JSON
【Snowflake Snow Snowflakes(最小表示法+Hash)】 最小表示法模板,求字符串循环同构的最小字典序表示。 核心函数: int sakura(int a[]) — 后缀数组 uLL Hash(int a[],int st) — 哈希计算 uLL find(int a[]) — 查找(并查集寻根/二分查找)
C++ 43 行 CPP
#include<algorithm>
#include<cstdio>
#include<map>
#define R register int
#define uLL long long
int n,t,p=13333331,re,A[13];
std::map<uLL,int>pan;
inline int sakura(int a[]){
    R i=1,j=2,k;
    while(i<=6&&j<=6){
        k=0;
        while(k<6&&a[i+k]==a[j+k])++k;
        if(k==6)break;
        if(a[i+k]>a[j+k]){i+=k+1;if(i==j)++i;}
        else{j+=k+1;if(i==j)++j;}
    }
    return i<j?i:j;
}
inline uLL Hash(int a[],int st){
    R i=0;uLL x=0;
    for(;i<6;++i)x=x*p+(uLL)a[st+i];
    return x;
}
inline uLL find(int a[]){
    R x,y,i=1,k=0,b[13];
    for(;i<=6;i++)b[i]=a[7-i];
    for(i=1;i<=6;i++)a[i+6]=a[i],b[i+6]=b[i];
	x=sakura(a),y=sakura(b);
    for(i=0;i<6;i++)
		if(a[x+i]<b[y+i])return Hash(a,x);
		else if(a[x+i]>b[y+i])return Hash(b,y);
    return Hash(a,x);
}
int main(){
    scanf("%d",&n);R i,j;
    for(i=1;i<=n;i++){
        for(j=1;j<=6;j++)scanf("%d",&A[j]);
        uLL re=find(A);
        if(pan[re]){printf("Twin snowflakes found.");return 0;}
    	pan[re]=1;
	}
    printf("No two snowflakes are alike.");
}
最小表示法 工艺
30 行
CPP JSON
【最小表示法(工艺)】 最小表示法模板,求字符串循环同构的最小字典序表示。 核心函数: void in(Re &x) — 核心算法函数 关键配置: N=3e5+5
C++ 29 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=3e5+5;
int n,s[N<<1];
inline void in(Re &x){
    Re f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int main(){
	in(n);
	for(Re i=1;i<=n;++i)in(s[i]),s[i+n]=s[i];
	Re i=1,j=2;
	while(i<=n&&j<=n){
		Re k=1;
		while(k<=n&&s[i+k-1]==s[j+k-1])++k;
		if(k>n)break;
		if(s[i+k-1]>s[j+k-1])i+=k;
		else j+=k;
		if(i==j)++i;
	}
	Re st=min(i,j);
	for(Re i=0;i<n;++i)printf("%d ",s[st+i]);
}
已复制