Hexo
0%

Posted on In , ,
Symbols count in article: 1.7k Reading time ≈ 2 mins.

树的直径

树上任意两节点之间最长的简单路径即为树的直径

两次DFS

若存在负权边，则无法使用两次DFS的方式求解直径

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
const int N = 10000 + 10;

int n, c, d[N];
vector<int> E[N];

void dfs(int u, int fa) {
  for (int v : E[u]) {
    if (v == fa) continue;
    d[v] = d[u] + 1;
    if (d[v] > d[c]) c = v;
    dfs(v, u);
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    E[u].push_back(v), E[v].push_back(u);
  }
  dfs(1, 0);
  d[c] = 0, dfs(c, 0);
  printf("%d\n", d[c]);
  return 0;
}

如果需要求出一条直径上所有节点，则可以在第二次DFS的过程中，记录每个点的前序节点，即可从直径的一端一路向前，遍历直径上所有的节点

树形dp

实现1

d1和d2分别为每个节点作为字树的根向下，所能延伸的最长路径长度d1与此长路径d2，那么直径就是对于每个点，该点d1+d2所能取到的值中的最大值

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
const int N = 10000 + 10;

int n, d = 0;
int d1[N], d2[N];
vector<int> E[N];

void dfs(int u, int fa) {
  d1[u] = d2[u] = 0;
  for (int v : E[u]) {
    if (v == fa) continue;
    dfs(v, u);
    int t = d1[v] + 1;
    if (t > d1[u])
      d2[u] = d1[u], d1[u] = t;
    else if (t > d2[u])
      d2[u] = t;
  }
  d = max(d, d1[u] + d2[u]);
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    E[u].push_back(v), E[v].push_back(u);
  }
  dfs(1, 0);
  printf("%d\n", d);
  return 0;
}
Read more »

Posted on In ,
Symbols count in article: 542 Reading time ≈ 1 mins.

z函数(扩展kmp)

对于一个长度为 n 的字符串 s，定义函数 z[i] 表示 s 和 s[i,n-1]（即以s[i] 开头的后缀) 的最长公共前缀(LCP) ，则 z 被称为 s 的 z 函数。特别的，z[0] = 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> z_function(string s) {
  int n = (int)s.length();
  vector<int> z(n);
  for (int i = 1, l = 0, r = 0; i < n; ++i) {
    if (i <= r && z[i - l] < r - i + 1) {
      z[i] = z[i - l];
    } else {
      z[i] = max(0, r - i + 1);
      while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
    }
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  }
  return z;
}

字符串整周期

给定一个长度为 n 的字符串 s，找到其最短的整周期，即寻找一个最短的字符串 t ，使得 s 可以被若干个 t 拼接而成的字符串表示。

考虑计算 s 的 Z 函数，则其整周期的长度为最小的 n 的因数 i ，满足 i + z[i] = n。

Read more »

Posted on In ,
Symbols count in article: 1k Reading time ≈ 1 mins.

kmp

next数组，对于模式串的某一位置 j ， next[j] 的值是该模式串从下标0到j-1的子串最大相等前缀和后缀数

1
2
3
s:       a b a a b c a b a
index:   0 1 2 3 4 5 6 7 8
next:	 -1 0 0 1 1 2 0 1 2
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int maxn = 1e5 + 10;
char a[maxn];//文本串
char b[maxn];//模式串
int kmp_next[maxn];

void get_next(int m)
{
    int j = 0;
    kmp_next[0] = 0;//初始化
    for (int i = 1; i <= m;++i)
    {
        //当这一位不匹配时，将j指向此为之前最大公共前后缀的位置
        while(j>0&&b[i]!=b[j])
            j = kmp_next[j-1];
        if (b[i] == b[j])//如果这一位匹配，那么将j+1，继续判断下一位
            ++j;
        kmp_next[i] = j;
    }
}

//找到b在a中第一次出现的位置
int find_pos(int n,int m)
{
    int i, j = 0;
    int p = -1;
    get_next(m);
    for (i = 0; i < n;++i)
    {
        while(j>0&&a[i]!=b[j]) j=kmp_next[j-1];
        if (a[i] == b[j]) ++j;
        if (j == m)
        {
            p = i - m + 1;
            break;
        }
    }
    //返回位置p的值
    return p;
}

//找到b在a中第k次出现的位置
int find_num(int n,int m,int k)
{
    int i, j = 0;
    int res = 0;
    get_next(m);
    for (i = 0; i < n;++i)
    {
        while(j>0&&a[i]!=b[j]) j=kmp_next[j-1];
        if (a[i] == b[j]) ++j;
        if (j == m)
            ++res;
    }
    //返回数量
    return res;
}
Read more »

Posted on In ,
Symbols count in article: 2.9k Reading time ≈ 3 mins.

自动机

给定n个模式串和11个文本串，求有多少个模式串在文本串里出现过。(出现多次只算一次)

前置技能

1.Trie

2.KMP思想

1
2
3
4
5
6
7
8
struct note{
    int son[26];//26个英文字母
    int flag;//标记是否是末端
    int fail;//fail指针
}trie[maxn];
int n,cnt;
string s;
queue<int>q;

我们将n个模式串建成一颗Trie树，建树的方式和建Trie完全一样

1
2
3
4
5
6
7
8
9
10
11
12
void insert(string s)//构建trie
{
    int u=1;
    for(int i=0;i<s.length();++i)
    {
       int v=s[i]-'a';
       if(!trie[u].son[v])
       trie[u].son[v]=++cnt;
       u=trie[u].son[v];
    }
    trie[u].flag++;
}

img

假如我们现在有文本串ABCDBC

Read more »

Posted on In ,
Symbols count in article: 847 Reading time ≈ 1 mins.

字符串哈希

快速判断两个字符串是否相等

遇见不定长问题可以通过

单hash

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
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int maxn = 1e5 + 10;
ull hash_[maxn], xp[maxn];

void init()
{
    xp[0] = 1;
    for (int i = 1; i <= maxn; ++i)
        xp[i] = xp[i - 1] * 13331;
    return;
}

void make_hash(string s)
{
    int len = s.length();
    hash_[len] = 0;
    for (int i = len - 1; i >= 0; i--)
    {
        hash_[i] = hash_[i + 1] * 13331 + s[i] - 'A' + 1;
    }
    return;
}

ull get_hash(int l, int len) // 得到起点为l,长度为len的子串的哈希值
{
    return hash_[l] - hash_[l + len] * xp[len];
}

hash的应用

  • 字符串匹配

  • 允许k次失配的字符串匹配

    • 给定定长为n的源串s，以及长度为m的模式串p，要求查找源串中有多少字串与模式串匹配；s与p匹配，当且仅当s与p长度相同，且最多有k个位置字符不同
    • 哈希+二分

  • 最长公共子字符串

    • 给定 m 个总长不超过 n 的非空字符串，查找所有字符串的最长公共子字符串，如果有多个，任意输出其中一个。
    • 很显然如果存在长度为 k 的最长公共子字符串，那么 k-1 的公共子字符串也必定存在。因此我们可以二分最长公共子字符串的长度。假设现在的长度为 k ，check(k) 的逻辑为我们将所有所有字符串的长度为 k 的子串分别进行哈希，将哈希值放入 n 个哈希表中存储。之后求交集即可。

  • 最长回文子串

    • 二分答案

  • 确定字符串中不同子字符串的数量

Read more »