首页 > 其他分享 >回文自动机

回文自动机

时间:2022-11-21 12:33:52浏览次数:80  
标签:Luogu 最小 len 广义 自动机 回文

回文自动机有些很优秀的性质。

广义回文自动机

你现在要对多个串建回文自动机,一个一个直接插进回文自动机里是对的。

(也就是广义后缀自动机假掉的那种建法)

例:Luogu P5555

最小回文循环节

事实上就是 border 理论那套。

考虑回文自动机上的一个节点 \(x\),那么他的最小回文循环节长度就是 \(len[x]-len[fail[x]]\)(如果存在)。

存在性也是好判的。

例:Luogu P4287


有了这两个性质,它可以很方便地处理一些回文相关的计数题,比如这道题(需要权限)。

标签:Luogu,最小,len,广义,自动机,回文
From: https://www.cnblogs.com/Nesraychan/p/16911069.html

相关文章

  • 【学习笔记】AC自动机常用技巧汇总
    \(\text{AC}\)自动机常用技巧汇总参考文章:自动机相关byAlex_Wei相关题目与题解:杂题20221.\(\text{AC}\)自动机上\(\text{dp}\)常用与限制长度与字典的字符串计数......
  • 最长回文串 香槟塔
    409.最长回文串Map<Character,Integer>map=newHashMap<>();char[]str=s.toCharArray();for(inti=0;i<s.length();i++){map.put(str[i],map.getOrDef......
  • 反转字符串中的单词 同构字符串 验证回文串
    151.反转字符串中的单词s=s.trim();先清除前后空格String[]sb=s.split("");StringBuilderans=newStringBuilder();for(inti=sb.length-1;i>0;i--)......
  • AC自动机
    #include<cstdio>#include<cstring>#include<cstdio>#include<queue>#definemaxn1000039usingnamespacestd;chars[maxn],key[maxn];queue<int>q;inttrie[maxn][26]......
  • 回文串
        这道题目我直接在程序上注释了:1#include<bits/stdc++.h>2usingnamespacestd;3intmain()4{5intt123123123123123123,a,b;6cin>......
  • 循环练习-判断回文数
    Scanners=newScanner(System.in);//引用键盘录入功能System.out.println("本程序用于判断回文数,请输入您要判断的值:");intx=s.nextInt();//将键盘输入的......
  • 线性DP-2472. 不重叠回文子字符串的最大数目
    问题描述给你一个字符串s和一个正整数k。从字符串s中选出一组满足下述条件且不重叠的子字符串:每个子字符串的长度至少为k。每个子字符串是一个回文串......
  • AC自动机
    AC自动机以trie为基础,首先将若干模式串插入trie树中,之后构建fail指针和AC自动机,即由trie树变为trie图。fail指针的定义是,对于当前点x,从根到x形成的字符串为s,x的fail指针指......
  • 回文树
    回文树(EERTree,PalindromicTree)亦称回文自动机,用于存储一个串中的所有回文子串。由于回文串可能有奇有偶,于是分为两棵树进行构建,偶跟编号为0,长度为0,fail指向奇根,奇根编......
  • AC 自动机——trie 树与 KMP 算法的结合体
    默认所有字符串的下表从\(1\)开始。梗概与实现如果是单一的模式串和字符串进行匹配,KMP算法自然可以派上用场。但如果有多个模式串呢?对每个模式串都跑一遍KMP?如果有......