发布时间：2024-04-24

哈希+二分判断字符串大小 $O(logn)$

要点：二分找出最长公共前缀(LCP)，然后比较下一位的大小
通常选取base=131，数据类型为unsigned long long

EOJ3427 Suffix

题意：

给定n个字符串，从每个字符串选出若干个后缀(不能为空)组成字符串，找出字典序最小的

思路：

考虑从后往前插入，找出字典序最小的位置，并插入

cpp

ULL H[N],pw[N],B=131;
char ans[N];
void init(){
    pw[0]=1;
    for(int i=1;i<=5e5;i++)pw[i]=pw[i-1]*B;
}
ULL get(int l,int r){
    return H[r]-H[l-1]*pw[r-l+1];
}
bool cmp(int x,int y){
    int l=1,r=y;
    while(l<r){
        int mid=l+r>>1;
        if(get(x-mid+1,x)==get(y-mid+1,y))l=mid+1;
        else r=mid;
    }
    return ans[x-l+1]<ans[y-l+1];
}
void solve(){
    init();
    int n;
    cin>>n;
    vector<string> str(n+1);
    for(int i=1;i<=n;i++)cin>>str[i];
    int end=0;
    for(int i=n;i>=1;i--){
        int len=str[i].size();
        ans[++end]=str[i][len-1];
        H[end]=H[end-1]*B+str[i][len-1];
        int t=end;
        int step=1;
        for(int j=len-2;j>=0;j--,step++){
            ans[end+step]=str[i][j];
            H[end+step]=H[end+step-1]*B+str[i][j];
            if(cmp(end+step,t))t=end+step;
        }
        end=t;
    }
    for(int i=end;i>=1;i--)cout<<ans[i];
}

2023CCPC深圳相似基因序列

题意：

给定 $N,Q,M,K (1 \leq N,Q \leq 100 ,1 \leq M \leq 60000 , 1 \leq K \leq 10)$
N个长度为M的字符串，Q次询问,每次询问给定一个长度为M的字符串，问有多少个字符串与其相似(最多有k个不同的字符)

思路：

考虑二分+哈希
预处理为 $O(NM)$
二分查找为 $O(QNlogM)$

cpp

ULL pw[N],B=131;
void init(){
	pw[0]=1;
	for(int i=1;i<=6e4;i++)pw[i]=pw[i-1]*B;
}
int n,q,m,k;
ULL get_H(int l,int r,vector<ULL>&H){
	return H[r]-H[l-1]*pw[r-l+1];
}
void solve(){
	init();
	cin>>n>>q>>m>>k;
	vector<string> a(n+1);
	vector<vector<ULL>> hsh(n+1,vector<ULL>(m+1));
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]=" "+a[i];
		for(int j=1;j<=m;j++)hsh[i][j]=hsh[i][j-1]*B+a[i][j];
	}
	while(q--){
		string s;
		cin>>s;
		s=" "+s;
		vector<ULL> hs(m+1);
		for(int i=1;i<=m;i++)hs[i]=hs[i-1]*B+s[i];
		int cnt=0;
		for(int i=1;i<=n;i++){
			int step=1;
			int x=0;
			while(step<=m){
				int l=1,r=m-step+1;
				while(l<r){
					int mid=l+r>>1;
					if(get_H(step,step+mid-1,hsh[i])==get_H(step,step+mid-1,hs))l=mid+1;
					else r=mid;
				}
				if(get_H(step,step+l-1,hsh[i])==get_H(step,step+l-1,hs))break;
				step=step+l;
				x++;
				if(x>k)break;
			}	
			if(x<=k)cnt++;
		}
		cout<<cnt<<"\n";
	}
}

CF1393E(黑题)

题意：
给你n个字符串，对每个字符串，你可以删除其任意一个字符或让其保持原样，求最后使得字符串字典序不降得方案数
$1 \leq N \leq 10^5 ,1 \leq \sum |S| \leq 10^6$
思路：
首先容易想到状态方程: $f_{i,j}=\sum_{满足题意的s_{i,j},s_{i-1,k}} f_{i-1,k}$

暴力转移的时间复杂度为 $O(L^3)$
考虑优化，比较用字符串+哈希优化，排序可以用类似[P5329]的方法线性排序，时间复杂度 $O(LlogL)$

cpp

ULL pw[N],B=131;
vector<ULL> H[N];
vector<int> order[N];
int len[N];
LL f[2][N];
void init(){
    pw[0]=1;
    for(int i=1;i<=1e6+3;i++)pw[i]=pw[i-1]*B;
}
ULL get_H(int id,int l,int r){
    if(l>r)return 0;
    return H[id][r]-H[id][l-1]*pw[r-l+1];
}
void Sort(vector<int>&tmp,string &s,int n){
    int id=1,l=1,r=n;
    for(int i=2;i<=n;i++){
        if(s[i-1]<s[i]){
            for(int j=i-1;j>=id;j--)tmp[r--]=j;
            id=i;
        }
        if(s[i-1]>s[i]){
            for(int j=id;j<i;j++)tmp[l++]=j;
            id=i;
        }
    }
    for(int i=id;i<=n;i++)tmp[l++]=i;
}
ULL get(int id,int x,int mid){
    if(mid<=x-1)return H[id][mid];
    int d=mid-x+1;
    ULL tmp=get_H(id,x+1,x+d);
    return tmp+H[id][x-1]*pw[d];
}
bool cmp(int idx,int ox,int idy,int oy,string &x,string&y){
    int l=1,r=min(len[idx]-1,len[idy]-1),tmp=r;
    while(l<r){
        int mid=l+r>>1;
        if(get(idx,ox,mid)==get(idy,oy,mid))l=mid+1;
        else r=mid;
    }
    if(get(idx,ox,l)==get(idy,oy,l))return len[idx]-(ox<len[idx])<=len[idy]-(oy<len[idy]);
    return x[l+(l>=ox)]<=y[l+(l>=oy)];
}
void solve(){
    init();
    int n;
    cin>>n;
    vector<string> s(n+1);
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]+='#';
        len[i]=s[i].size();
        s[i]=" "+s[i];
        H[i].resize(len[i]+1);
        order[i].resize(len[i]+10);
        Sort(order[i],s[i],len[i]);
        for(int j=1;j<=len[i];j++)H[i][j]=H[i][j-1]*B+s[i][j];
    }
    for(int i=1;i<=len[1];i++)f[1][i]=1;
    for(int i=2;i<=n;i++){
        LL sum=0;
        int k=0;
        for(int j=1;j<=len[i];j++){
            while(k+1<=len[i-1]&&cmp(i-1,order[i-1][k+1],i,order[i][j],s[i-1],s[i])){
                k++;
                sum+=f[i-1&1][order[i-1][k]];
                sum%=mod;
            }
            f[i&1][order[i][j]]=sum;
        }
    }
    LL ans=0;
    for(int i=1;i<=len[n];i++)ans+=f[n&1][i],ans%=mod;
    cout<<ans<<"\n";
}

P5329 [SNOI2019] 字符串

题意：
对一个字符串删除任意一个字符后的字符串排序
思路：

假设前面都是相同的字符
如果此时s[i-1]>s[i]，那么前面无论删除哪个字符都比后面小，插入到开头
如果此时s[i-1]<s[i]，那么前面无论删哪个字符都比后面大，插入到尾部

cpp

void solve(){
    cin>>n;
    string s;
    cin>>s;
    int n=s.size();
    s=" "+s;
    vector<int> ans(n+1);
    int l=1,r=n,id=1;
    for(int i=2;i<=n;i++){
        if(s[i-1]<s[i]){
            for(int j=i-1;j>=id;j--)ans[r--]=j;
            id=i;
        }
        if(s[i-1]>s[i]){
            for(int j=id;j<=i-1;j++)ans[l++]=j;
            id=i;
        }
    }
    for(int i=id;i<=n;i++)ans[l++]=i;
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}

哈希+二分判断字符串大小 O(logn)O(logn)O(logn) ​

EOJ3427 Suffix ​

题意： ​

思路： ​

2023CCPC深圳 相似基因序列 ​