算法基础学习笔记——⑦KMP\Trie\并查集

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
     while (j && p[i] != p[j + 1]) j = ne[j];
     if (p[i] == p[j + 1]) j ++ ;
     ne[i] = j;
}
// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
     while (j && s[i] != p[j + 1]) j = ne[j];
     if (s[i] == p[j + 1]) j ++ ;
     if (j == m)
     {
         j = ne[j];
         // 匹配成功后的逻辑
     }
}

//一般有26个字母 //idx存的是当前用到的下标
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量
// 插入一个字符串
void insert(char *str)
{
     int p = 0;//p为节点 
     for (int i = 0; str[i]; i ++ )
     {
         int u = str[i] - 'a';//将a～z映射成0～25
         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]; i ++ )
     {
         int u = str[i] - 'a';
         if (!son[p][u]) return 0;
         p = son[p][u];
     }
     return cnt[p];
}

int p[N]; //存储每个点的祖宗节点
 // 返回x的祖宗节点
 int find(int x)
 {
     if (p[x] != x) p[x] = find(p[x]);
     return p[x];
 }
 // 初始化，假定节点编号是1~n
 for (int i = 1; i <= n; i ++ ) p[i] = i;
 // 合并a和b所在的两个集合：
 p[find(a)] = find(b);

 int p[N], size[N];
 //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
 // 返回x的祖宗节点
 int find(int x)
 {
     if (p[x] != x) p[x] = find(p[x]);
     return p[x];
 }
 // 初始化，假定节点编号是1~n
 for (int i = 1; i <= n; i ++ )
 {
     p[i] = i;
     size[i] = 1;
 }
 // 合并a和b所在的两个集合：
 size[find(b)] += size[find(a)];
 p[find(a)] = find(b);

int p[N], d[N];
 //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
 // 返回x的祖宗节点
 int find(int x)
 {
     if (p[x] != x)
     {
         int u = find(p[x]);
         d[x] += d[p[x]];
         p[x] = u;
     }
    return p[x];
 }
 // 初始化，假定节点编号是1~n
 for (int i = 1; i <= n; i ++ )
 {
     p[i] = i;
     d[i] = 0;
 }
 // 合并a和b所在的两个集合：
 p[find(a)] = find(b);
 d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量