蓝月の笔记——字符串篇

摘要

一些串串
\(\quad\qquad\)——某yl新高一学长
字串
\(\quad\qquad\)——某yl新高一学长のppt

Warning

本文中字符串的下标有时从 \(1\) 开始有时从 \(0\) 开始，请自行分辨无特殊说明从 \(1\) 开始

字符串长度无特殊说明为 \(n\)

字符串无特殊说明表示为 \(s\)

Part 1 概念

相信读者都知道字符串的概念了，那就只快速过一遍

子序列和子串都是原串的一部分，字串要求连续，子序列只要求保证相对位置即可

前缀是从 \(1\) 开始的子串，后缀是以 \(n\) 结尾的子串，真（前/后）缀为不是本身的（前/后）缀

回文串是满足 \(\forall i \in [1,n],s_i=s_{n-i+1}\)，即正反看都一样，如 acbca

Part 2 字典树 Trie

原本读音和 tree 一样，为了区分读作 trai

先上图：

这是一颗存储了字符串 abc，ac，b，bb，c 的字典树

在字典树中，边代表字符，点只是用来连接的。也可以把边和点换过来，只不过根节点不方便存储，不做考虑