模板-字符串

发表于 更新于 分类于

字符串哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using ull = unsigned long long;
const int P = 131;
int n;
char str[N];
ull h[N], p[N];

ull HASH(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

void init()
{
    p[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + str[i];
    }
}

trie

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
const int N = 100010;
int son[N][26], cnt[N], idx;
char str[N];

void insert(char str[])
{
    int p = 0;
    for (int i = 0; str[i] != 0; i++)
    {
        int u = str[i] - 'a';
        if (!son[p][u])
            son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
}

int query(char str[])
{
    int p = 0;
    for (int i = 0; str[i] != 0; i++)
    {
        int u = str[i] - 'a';
        if (!son[p][u])
            return 0;
        p = son[p][u];
    }
    return cnt[p];
}

kmp

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
const int N, M;
int n, m;
char p[N],s[M];
void init()
{
    ne[0] = -1;
    for (int i = 0, j = -1; i < n;)
    {
        if (j == -1 || p[i] == p[j])
        {
            ++i, ++j;
            ne[i] = j;
        }
        else
            j = ne[j];
    }
}

void kmp()
{
    for (int i = -1, j = -1; i < m;)
    {
        if (j == -1 || p[j] == s[i])
            ++i, ++j;
        else
            j = ne[j];
        
        if (j == n)
        {
            // do something such as:
            cout << i - j << " ";
        }
    }
}