uniHk

回文自动机

01Trie(5) AC自动机(7) CDQ分治(4) dsu on tree(1) K-D Tree(5) 主席树(5) 各类说明(1) 后缀数组(1) 后缀自动机(11) 字符串（杂）(6) 康托展开(1) 数学(7) 整体二分(1) 斜率优化DP(3) 树链剖分(3) 概率DP(2) 算法(Lazy)(38) 线性基(5) 莫队(6) 计算几何(3)

/ 注册

全部文章 / 回文自动机（共6篇）

回文自动机

回文自动机小小总结：别忘了写上初始化！当字符串下标从 0 0 0开始时， ...

2020-01-02

0 471

洛谷-P4287 双倍回文(回文自动机)

双倍回文刚刚用Manacher写了一遍这个题，现在换种写法，舒服！！！优美的half数组求法（Manacher的简单写法请走这里) 题意：若一个回文串左半部分和右半部分分别为一个回文串，则这个回文串被称为双倍回文串(这名字有点傻呀！)。求：给定一个回文串，问最长的双倍回文串有多长。思路：...

2020-01-02

0 588

Virus synthesis（回文自动机，DP）

Virus synthesis 回文自动机好题！题意：初始有一个空串，然后通过两种操作得到目的串t，求最少操作数。两种操作分别为：在字符串前面或者后面任意加一个字符在字符串前面或者后面加上当前字符串的镜像思路：思考一下，花费（操作数）要最小（少），那肯定操作2...

2020-01-02

0 467

牛客多校2019-6C-Palindrome Mouse（回文自动机+统计支配点）

Palindrome Mouse 题意：若把给定字符串的所有不同回文子串放到一个集合内，求集合内有多少对回文子串满足其中一个是另一个的子串。思路：建好回文自动机若设 a ...

2020-01-02

0 467

Colorful String（2019徐州网络赛）（回文自动机上dfs+状压）

Colorful String 比赛一开，我看的第一题就是这题。然后一看，回文串！那肯定回文自动机搞一下不就行了吗？再仔细一看，发现有个小地方我不敢确定，遂想用 m ...

2020-01-02

0 419

秩序魔咒（回文自动机+最长公共回文子串）

秩序魔咒题意：求两个串最长相同的回文子串的长度，并求出这种长度的子串有多少个思路：既然有回文串，自然会想到回文自动机或 m a ...

2020-01-02

0 545