yuzh的博客

❤ ECUST ❤

0%

字符串基础

发表于 更新于 Valine：

字符串哈希

定义

字符串哈希就是通过一种计算方法，将每个不同的字符串映射成不同的数值。

算法流程

  1. 把字符串映射成一个 p 进制数字。
    对于一个长度为 n 的字符串 s，
    这样定义 Hash 函数：h(s) = ∑(i=1 to n) s[i] × p^(n-i) (mod M)
    例如，字符串 abc，其哈希函数值为 a*p^2 + b*p^1 + c
    即 97 × 131^2 + 98 × 131^1 + 99
  2. 如果两字符串不一样，Hash 函数值却一样，这样的现象称为哈希碰撞。
  3. 解决哈希碰撞的方法：
    (1) p 通常取质数 131 或 13331
    (2) M 通常取大整数 2^64，把哈希函数值 h 定义为 ULL，超过则自动溢出，等价于取模。

求一个字符串的哈希值相当于求前缀和，求一个字符串的子串的哈希值相当于求区间和。

最小表示法

定义

当字符串 S 中选定一个位置 i 满足 S[in] + S[1i-1] = T，则 T 是 S 的循环同构串。

设 S = “BCAD”，其循环同构串有“BCAD”、“CADB”、“ADBC”、“DBCA”， 当 i=3 时，得到字典序最小的循环同构串是“ADBC”。

最小表示法就是找出字符串 S 的循环同构串中字典序最小的那一个。

对于循环串（或环），通常的技巧就是复制一倍，破环成链，然后扫描。 用三个变量指针控制扫描，指针 i,j 控制匹配起始位置，指针 k 控制匹配长度。

算法流程

  1. 把字符串复制一倍
  2. 初始化指针 i=1，j=2，匹配长度k=0；
  3. 比较s[i+k]和s[j+k]是否相等，
    (1)s[i+k]==s[j+k]，则 k++;
    (2)s[i+k]>s[j+k]，则 i=i+k+1；
    (3)s[i+k]<s[j+k]，则 j=j+k+1；
    若跳转后两个指针相同，则 j++，以
    确保比较的两个字符串不同；
  4. 重复上述过程，直到比较结束；
  5. 答案为 min(i, j)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
#define MAXN 3000010
using namespace std;

int n,a[MAXN*2];
int i=1,j=2,k=0;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i+n]=a[i];
    }
    while(i<=n && j<=n)
    {
        if(i==j)
        {
            j++;
            continue;
        }
        int k=0;
        while(k<n)
        {
            if(a[i+k]==a[j+k]) k++;
            else break;
        }
        if(a[i+k]>a[j+k]) i+=k+1;
        else j+=k+1;
    }
    int s;
    if(a[i]>a[j]) s=j;
    else s=i;
    for(int t=0;t<n;t++)
    {
        cout<<a[s+t]<<" ";
    }
    return 0;
}

KMP

给定一个模式串P和一个主串S，求模式串P在主串S中出现的位置。（字符串的下标均从1开始）

  1. 取最长的相等前后缀，可以保证不漏解。
  2. 通过模式串前后缀的自我匹配的长度，计算 next 函数，给 j 指针打一张表，失配时就跳到 next[j] 的位置继续匹配。

next函数

next[i] 表示模式串 P[1..i] 中相等前后缀的最长长度

P a a b a a b a a a a
ne[1]=0 a
ne[2]=1 a a
ne[3]=0 a a b
ne[4]=1 a a b a
ne[5]=2 a a b a a
ne[6]=3 a a b a a b
ne[7]=4 a a b a a b a
ne[8]=5 a a b a a b a a
ne[9]=2 a a b a a b a a a
ne[10]=2 a a b a a b a a a a

定义双指针：i 扫描模式串，j 扫描前缀。
初始化，ne[1]=0, i=2, j=0。
每轮 for 循环，i 向右走一步。

  1. 若 P[i]!=P[j+1]，让 j 回跳到能匹配的位置，
    如果找不到能匹配的位置，j 回跳到 0。
  2. 若 P[i]==P[j+1]，让 j+1，指向匹配前缀的末尾。
  3. next[i] 等于 j 的值。
1
2
3
4
5
for(int i=2,j=0;i<=n;i++){
    while(j && p[i-1]!=p[j]) j=nxt[j];
    if(p[i-1]==p[j]) j++;
    nxt[i]=j;
}

next函数过程

模式串与主串匹配

双指针：i 扫描主串，j 扫描模式串。
初始化，i=1, j=0。
每轮 for，i 向右走一步。

  1. 若S[i]!=P[j+1]，让 j 回跳到能匹配的位置，
    如果找不到能匹配的位置，j 回跳到 0。
  2. 若S[i]==P[j+1]，让 j 向右走一步。
  3. 若匹配成功，输出匹配位置。
1
2
3
4
5
for(int i=1,j=0;i<=m;i++){
    while(j && s[i-1]!=p[j]) j=nxt[j];
    if(s[i-1]==p[j]) j++;
    if(j==n) cout<<i-n+1<<endl;
}

模式串匹配过程