首页 > 其他分享 >CF1037H Security

CF1037H Security

时间:2024-04-05 17:44:43浏览次数:24  
标签:return SAM int CF1037H read endpos ans Security

\(CF1037H\ \ Security\)

题意

给定一个母串 \(s\) 和 \(T\) 次询问,每次询问 \(S[l\dots r]\) 中字典序严格大于 \(t\) 的最小串,没有则输出 \(-1\)

\[|s| \leq 10^5\ ,\ \sum |t| \leq 2 \times 10^5 \]

思路分析

不会,贺了

首先,因为这个题的标签里有SAM,所以我们要用SAM

首先我们考虑无 \(l,r\) 限制,很明显将 \(t\) 在母串 \(s\) 的 \(SAM\) 上跑。设答案串为 \(ans\), \(ans\) 与 \(t\) 匹配位数为 \(i\) 位(\(ans\) 与 \(t\) 前 \(i\) 位相同),那么一定有:

  1. \(ans[i+1] > t[i+1]\)

  2. 在满足 \(1\) 时令 \(i\) 最大,\(ans[i+1]\) 最小

此题难点就在于高贵的 \([l,r]\) 限制,除了满足上面两条,还有:

  1. 串 \(ans\) 包含于 \([l,r]\),此时 \(ans\) 的 \(endpos\) 要介于 \([l+len_{ans}\ ,\ r]\) 之间,我们只要 \(judge\) 每个 \(ans\) 即可

问题来了,如何 \(judge ?\)

首先考虑一个推论:

推论:对于后缀树上的某节点 \(u\),他的 \(endpos\) 集合为其子树的并集,即:

\[endpos(u)=\bigcup_{v\in son[u]} endpos(v) \]

当然,我们还应加上以 \(u\) 结尾的最长子串的 \(endpos\)

证明:

什么都证明只会害了你。 ——\(Shadow\)

开玩笑的

对于两个子串 \(S1,S2\),若 \(|S1|<|S2|\) ,且 \(S1\) 是 \(S2\) 的后缀,就必然有

\[endpos(s1)\varsubsetneq endpos(s2) \]

这个结论熟悉吧,最开始学 \(SAM\) 的时候,这是某个引理。那么根据后缀树后缀链接的定义,\(S_u\) 一定是 \(S_v\) 的后缀 \((v\in son[u])\),那么推论显然得证。

这样描述不太直观 很不直观可以画画图,比如串 "\(spxssspxx\)" (不要管 spx 是谁),我们构建出它的 \(SAM\),写出所有子串,如图:


其后缀树长这个样子


那么我们再耐心地标出每个节点的 \(endpos\) 集合,就成了这个样子:


鸣谢@k8He画图网站


好了,那么到此就差不多了,上文因我语文功底有限,叙述可能不太清楚,所以——

领会精神吧~!

好,对于具体的实现,我们让每个节点只保留最长串(即从根节点到它的最长路径)的 \(endpos\),然后对于一个非叶节点,我们通过线段树合并来求解它的 \(endpos\) 集合,最后 \(judge\) 是否存在 \([l+i-1,r]\) 内的 \(endpos\) 即可。

\(AC\ \ code\)

#include<bits/stdc++.h>
using namespace std;

#define read read()
#define pt puts("")
inline int read
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x)
{
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
#define N 200010

int n,m;
char s[N];
int len[N<<1],link[N<<1];
int ch[N<<1][27];
vector<int >son[N<<1];
int tot,last;
int ans[N<<1];
int siz;
int root[N<<5];
int ls[N<<5],rs[N<<5];

void add(int &rt,int l,int r,int x)
{
    if(!rt)  rt=++siz;
    if(l==r)  return;
    int mid=(l+r)>>1;
    if(x<=mid)  add(ls[rt],l,mid,x);
    else  add(rs[rt],mid+1,r,x);
}

void extend()
{
    for(int i=0;i<n;i++){
        int c=s[i]-'a'+1;
        int p=last,cur=++tot;
        len[cur]=len[p]+1;
        add(root[cur],1,n,len[cur]);
        while(p!=-1 && !ch[p][c]){
            ch[p][c]=cur;
            p=link[p];
        }
        if(p==-1)  link[cur]=0;
        else{
            int q=ch[p][c];
            if(len[q]==len[p]+1)  link[cur]=q;
            else{
                int copy=++tot;
                link[copy]=link[q];
                len[copy]=len[p]+1;
                for(int i=1;i<=26;i++)  ch[copy][i]=ch[q][i];
                while(p!=-1 && ch[p][c]==q){
                    ch[p][c]=copy;
                    p=link[p];
                }
                link[cur]=link[q]=copy;
            }
        }
        last=cur;
    }
    for(int i=1;i<=tot;i++)  son[link[i]].push_back(i);
}//构造sam

bool judge(int rt,int l,int r,int ql,int qr)
{
    if(!rt)  return 0;
    if(ql<=l&&r<=qr)  return 1;
    int mid=(l+r)>>1;
    bool res=0;
    if(ql<=mid)  res=res|judge(ls[rt],l,mid,ql,qr);
    if(res)  return 1;
    if(qr>mid)  res=res|judge(rs[rt],mid+1,r,ql,qr);
    return res;
}

int merge(int x,int y)
{
    if(!x)  return y;
    if(!y)  return x;
    int rt=++siz;
    ls[rt]=merge(ls[x],ls[y]);
    rs[rt]=merge(rs[x],rs[y]);
    return rt;
}

void dfs(int x)
{
    for(int y:son[x]){
        dfs(y);
        root[x]=merge(root[x],root[y]);
    }
}

signed main()
{
    scanf("%s",s);
    n=strlen(s);
    link[0]=-1;
    extend();
    dfs(0);
    int T;T=read;
    int ql,qr,p;
    char t[N<<1];
    while(T-->0)
    {
        ql=read;qr=read;p=0;
        scanf("%s",t+1);
        m=strlen(t+1);
        int end=m+1;
        for(int i=1;i<=m+1;i++){//遍历到m+1,因为如果所有位都匹配上了,我们显然还要再找一位才能使字典序大于t
            ans[i]=-1;
            //遍历到前i位匹配
            for(int c=max(1,t[i]-'a'+1+1);c<=26;c++){
                //因为字典序要严格大于t,所以从t[i]-'a'+2开始
                int v=ch[p][c];
                if(v && judge(root[v],1,n,ql+i-1,qr)){
                    ans[i]=c;
                    break;
                }
            }
            p=ch[p][t[i]-'a'+1];
            if(!p || !judge(root[p],1,n,ql+i-1,qr)){
                end=i;
                break;
            }
        }
        while(ans[end]==-1 && end)  end--;
        if(!end)  puts("-1");
        else{
            for(int i=1;i<end;i++)  putchar(t[i]);
            putchar(ans[end]+'a'-1);pt;
        }
    }

    return 0;
}

本人刚学 \(SAM\),题解存在疏漏还请指出(拜谢

标签:return,SAM,int,CF1037H,read,endpos,ans,Security
From: https://www.cnblogs.com/lty-ylzsx/p/18114445

相关文章

  • springboot security对接mysql数据库
    首先要添加springbootsecurity依赖<dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-security</artifactId><version>3.2.4</version></dependenc......
  • SpringSecurity认证和授权流程详解
    什么是SpringSecuritySpringSecurity是一个Java框架,用于保护应用程序的安全性。它提供了一套全面的安全解决方案,包括身份验证、授权、防止攻击等功能。SpringSecurity基于过滤器链的概念,可以轻松地集成到任何基于Spring的应用程序中。它支持多种身份验证选项和授权策略,开发人员......
  • spring security 6.0.8(boot 3.0.13)自定义 filter 踩坑-已解决
    springboot3.0.13(3.1.10)springsecurity6.0.8(6.1.8)-- 官方文档:https://docs.spring.io/spring-security/reference/index.html写文时最新为6.2.3。  说明,先是用springboot3.1.10测试,失败,降低到3.0.13仍然失败。 开发建立了AppLoginFilter,实现了attemp......
  • 12.Springsecurity简单总结
    关于springsecurity的介绍后面我接触的应该是这个和Shiro!!!一个网站很重要很重要的是安全问题(狂神说的)哈哈我觉得更重要的是编写吧来看吧maven依赖这个肯定很重要thymeleaf依赖就跳过了这个东西应该很重要我学到现在一直离不开当然我还是没完全搞懂语法嘞就像jsp......
  • 【SpringSecurity】基础入门
    目录权限管理什么是权限管理认证授权权限管理解决方案Shiro开发者自定义SpringSecuritySpringSecurity特性Spring、SpringBoot和SpringSecurity三者的关系整体架构1.认证AuthenticationManagerAuthenticationSecurityContextHolder2.授权AccessDecisionManage......
  • WAF-ModSecurity
    Web应用防护系统(WebApplicationFirewall,简称:WAF)代表了一类新兴的信息安全技术,用以解决诸如防火墙一类传统设备束手无策的Web应用安全问题与传统防火墙不同,WAF工作在应用层,因此对Web应用防护具有先天的技术优势。基于对Web应用业务和逻辑的深刻理解,WAF对来自Web应用程序客户......
  • System.Security.Cryptography.RijndaelManaged()
    以下为ai生成:System.Security.Cryptography.RijndaelManaged 是.NET框架中的一个加密类,用于提供高级加密标准(AES)算法的实现。AES是一种强大的对称加密算法,它可以用于保护数据的安全。以下是一个使用RijndaelManaged进行数据加密和解密的简单例子:usingSystem;usingSystem.I......
  • Spring Cloud整合Spring Security Oauth2
    前言在当今数字化时代,随着企业业务规模和复杂性的不断增加,传统的单体应用架构已经难以满足日益增长的需求。微服务架构的兴起,以其高度模块化、可扩展性和可维护性的优势,逐渐成为企业架构升级的首选方案。然而,随着微服务的普及,如何保障服务的安全性、实现用户身份的统一管理......
  • A LARGE LANGUAGE MODEL EVALUATION BENCHMARK AND BASELINE FOR CHINESE PUBLIC SECU
    本文是LLM系列文章,针对《CPSDBENCH:ALARGELANGUAGEMODELEVALUATIONBENCHMARKANDBASELINEFORCHINESEPUBLICSECURITYDOMAIN》的翻译。CPSDBENCH:中国公共安全领域的大型语言模型评估基准和基线摘要1引言2相关工作3方法4结果与分析5结论摘要大......
  • c#使用System.Security.Cryptography实现DES算法加密和解密
    c#使用System.Security.Cryptography实现DES算法加密和解密在加密过程中,通常会将原始数据转换为字节数组,然后对其进行加密。而在解密过程中,需要将加密后的数据解密为原始字节数组,然后进行相应的处理。//解密读取publicstaticstringDecrypt(stringdata){try{......