首页 > 其他分享 >String Record

String Record

时间:2024-05-22 22:07:42浏览次数:18  
标签:一个点 String ACAM dfs 我们 Record fail 节点

T1. P5840

算法:ACAM+BIT+树链剖分

自然地,我们会对 \(s_i\) 建 ACAM,然后建出一颗 fail 树。

此时我们考虑集合内加入一个新的字符串。每一个匹配到的点我们都会给从这个点一直到 fail 数的根节点上的的每一个点 \(+1\),但是每一个点只会加一遍。然后对于这棵树上的一个节点,他对最后答案的贡献即为他的子树内所有节点的和。显然的,复杂度会超标。

我们发现其实可以用树上差分来来维护这两个操作。由于一个点的子树的 dfs 序是连续的,所以对于第一种操作,我们在链的开始位置即为叶子结点 \(+1\),在链的终止位置的父亲 \(-1\) 即可。对于操作二,其实就是查询一个连续段的和。此时我们可以用 BIT 来维护。

接下来我们考虑一个链最后会加到那一个点。

由于我们碰到已经标记过得点,我们不会重复加。我们现对于所有需要加的点根据 dfs 需大小来排个顺序,所以终点就是这个点和上一个需要加的点的 lca 的儿子。这样这道题目就做完了。

code

标签:一个点,String,ACAM,dfs,我们,Record,fail,节点
From: https://www.cnblogs.com/Carousel/p/18207239

相关文章

  • 不好分类的好题Record
    这里装的是一些不太好分类的。problem1给你\(n\)个序列,第\(i\)个序列的长度为\(m_i\),要求在每个序列中选择一个数,每种选法的代价为选择的\(n\)个数之和,请求出代价前\(k\)小的方案的代价之和。\(1\len,k\le10^5,1\lem_i\le10\)。对于\(k\le500\)的情况......
  • Dictionary<string, object>
    Dictionary<string,object>dcic=JsonHelper.DataRowFromJSON(resultdepth);foreach(vardepthkeyindcic.Keys){if(depthkey.Contains("data")){Dictionary<str......
  • 5-Longest Palindromic Substring-最长回文串
    问题描述链接:https://leetcode.com/problems/longest-palindromic-substring/description/Givenastring s,return thelongest palindromicsubstringins解释:给定一个字符串,求其最长的回文串回文串:一个字符串,如果从左往右读和从左往右读读出来的序列是一样的,称......
  • Invalid URI at UnityEngineInternal.WebRequestUtils.MakeInitialUrl (System.Stri
    问题背景:有一个项目用到3d模型,原来访问地址用的是域名,访问老是报跨域问题,于是换成了内网地址这么一换问题来了,控制台直接报错 FormatException:InvalidURIatUnityEngineInternal.WebRequestUtils.MakeInitialUrl(System.StringtargetUrl,System.StringlocalUrl)[0......
  • STL | string
    string介绍c++支持两种类型的字符串,一以NULL结尾的c风格字符串;二string类型的字符串头文件string是basic_string类模板使用char特化的类型#include<string>typedefbasic_string<char,char_traits<char>,allocator<char>>string;初始化//默认string对象,长度为0str......
  • net.sf.jsqlparser.schema.Column.withColumnName(Ljava/lang/String;)Lnet/sf/jsqlpar
    https://blog.csdn.net/yuanzhugen/article/details/133648431 SpringBoot整合mybatisplus报错:net.sf.jsqlparser.schema.Column,isavailablefromthefollowinglocationsAnattemptwasmadetocallthemethodnet.sf.jsqlparser.schema.Column.withColumnName(Ljava/l......
  • Java中的这些String特性可能需要了解下
    先总结下,String类具有以下特性:不可变性(Immutable):String对象一旦创建就不能被修改。任何对String对象的操作都会返回一个新的String对象,原始对象保持不变。字符串表(StringTable):StringTable表是一种存储字符串常量的内存区域,它可以提高字符串的重用率和性能。在创建字符串时,如果......
  • WPF Color ColorConverter.ConvertFromString convert hex to readable color
    stringcolorStr="#FF00008B";ColorbrushColor=(Color)ColorConverter.ConvertFromString(colorStr);  usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.Threading.Tasks;usingSystem.Windows;us......
  • Uri.EscapeDataString 和 Server.UrlEncoding 的区别
    今天在iis中访问一个即含有空格又含有#的文件名时,通过iis直接访问都无法到达,显示404,即便是urlencode文件名后依然无济于事,最后通过gpt问到了答案。Uri.EscapeDataString和Server.UrlEncode是.NETFramework中用于URL编码的两个方法,它们有以下区别:命名空间和所属类:Uri.Es......
  • Use AOP to record system logs
    UsingAOPtoRecordSystemLogs:1.CustomAnnotationClassDefineacustomannotationclass:packagecom.java.common.annotion;importjava.lang.annotation.*;@Target({ElementType.METHOD,ElementType.PARAMETER})//Thisannotationappliestomethodsandp......