电子神大一日游

发表于 2025-04-07

电子神大一日游

阅读全文 »

字符串总结

发表于 2025-04-02 更新于 2025-04-07

字符串总结

（施工中）

感谢 DeepSeek 对本文写作的大力支持。

字符串

字符串是一串顺序排列的字符。（废话）

以下是一些有关字符串的定义：

下标（index）：位于字符串第个位置的字符下标为（本文采用 1-index）。
子串（substring）：对于任意取出下标范围为的字符依次排列即为一个子串，记为。
子序列（subsequence）：对于任意依次取出排列即为一个子序列。
前缀（prefix）：任意以开头的子串。特别的，当时，称之为真前缀。
后缀（suffix）：任意以结尾的子串。特别的，当时，称之为真后缀。
字典序：对于任意两个字符串，，称字典序小于当且仅当满足以下两个条件之一：
- 存在一个下标，使得，且。
- 。
回文：如果一个字符串等于它的翻转，称它为回文串。

哈希

哈希即映射算法，是整个 OI 界性价比最高的算法几乎没有之一，搭配二分食用后它可以用几乎为零的学习成本和较高的效率解决下文大部分高级算法能解决的问题。

映射

我们知道双射的定义：对于集合，如果存在关系使得中任意一个元素都在中存在且仅存在一个元素与之对应，这个映射就是一个双射。

但是真的要找这样的算法是非常难的，因此我们退一步，如果我们认为这个关系只有极小的概率能让中两个不同元素经过关系后得到相同的结果，那么它就是一个合适的哈希算法。

生活中存在一些这样的哈希算法，比如将快递映射到取件码，将学生映射到学号；也存在一些会发生冲突的哈希算法，比如如果将首字母作为一个人名字的哈希值，就会出现诸如“主席树”之类令人忍俊不禁的情况。

哈希的主要用途是牺牲极小的正确率，将原本需要高时间复杂度比较的元素映射到低时间复杂度比较。这个牺牲的正确率一般是可以计算的：如果将个元素映射到个空间，那么发生冲突的概率为；但是如果将个元素映射到个空间，就有高达的概率发生冲突（生日悖论）。因此选取合适的哈希算法与映射后的空间极为重要。

字符串哈希

字符串哈希是典型的降低比较时间复杂度的算法。

考虑下列问题：

求模式串在文本串中的出现次数。

如果使用朴素算法，就需要对字符串的每个位置都进行一次时间复杂度的匹配，最坏时间复杂度会达到。但是使用字符串哈希，就能将单次匹配的时间复杂度降低为，总时间复杂度。

常用的字符串哈希实际上进行了两次映射：先将字符串映射为（字符集大小）进制数，然后再用取模等方式将其映射到常常为位无符号整数的大小。

关于哈希的具体写法不再赘述。

// 1-indexed
const ll HM[2] = {1000000007, 1000000009};
const ll HB[2] = {911382629, 19260817};
const int M = 1e6 + 5;
// 1-indexed string

ull hb[2][M];

void init_hsh() {
    for (int j = 0; j < 2; ++j) {
        hb[j][0] = 1;
        for (int i = 1; i < M; ++i)
            hb[j][i] = hb[j][i - 1] * HB[j] % HM[j];
    }
}

typedef std::array<ull,2> pul;
template <typename Tp>void cmod(Tp &x,int p){x=(x%p+p)%p;}
struct shsh{
    private:
        vul h[2];
    public:
        shsh(int n,string s):h{vul(n+1),vul(n+1)}{
            for(int j=0;j<2;++j)
                for(int i=1;i<=n;++i)
                    h[j][i]=(h[j][i-1]*HB[j]%HM[j]+s[i])%HM[j];
        }
        pul hsh(int l,int r){
            int len=r-l+1;
            pul x;
            for(int i=0;i<2;++i){
                auto p=h[i][l-1]*hb[i][len]%HM[i];
                cmod(x[i]=h[i][r]+HM[i]-p,HM[i]);
            }
            return x;
        }
};