算法基础_数据结构【KMP + Trie 树 + 并查集】

#include <iostream>
using namespace std;

const int N = 100010, M = 1000010; // 定义数组的最大长度
int n, m;                           // n 是模式串 p 的长度，m 是主串 s 的长度
char p[N], s[M];                    // p 是模式串，s 是主串
int ne[N];                          // next 数组，用于 KMP 算法


int main()
{
    cin >> n >> p + 1 >> m >> s + 1;

    //构建 next 数组
    for (int i = 2, j = 0; i <= n; i++)
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j++;
        ne[i] = j;
    }

    //KMP 匹配过程
    for (int i = 1, j = 0; i <= m; i++)
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j++;
        if (j == n)// 如果 j == n，说明模式串 p 完全匹配
        {
            printf("%d ", i - n);// 输出匹配的起始位置（从 0 开始计数）
            j = ne[j];// 回退 j，继续寻找下一个可能的匹配
        }
    }

    return 0;
}

cin >> n >> p + 1 >> m >> s + 1;

#include <iostream>
using namespace std;

const int N = 100010; // Trie 树的最大节点数
int son[N][26];       // Trie 树的存储结构，son[p][u] 表示节点 p 的第 u 个子节点
int cnt[N];           // 记录以每个节点结尾的字符串的个数
int idx = 0;              // 当前 Trie 树中节点的编号，从 1 开始分配
char str[N];          // 用于存储输入的字符串

// 插入操作：将字符串 str 插入到 Trie 树中
void insert(char* str)
{
    int p = 0; // 从根节点开始
    for (int i = 0; str[i]; i++) 
    {
        int u = str[i] - 'a'; // 将字符转换为索引（0~25）
        if (!son[p][u]) son[p][u] = ++idx; // 如果子节点不存在，则创建新节点
        p = son[p][u]; // 移动到子节点
    }
    cnt[p]++; // 以当前节点结尾的字符串计数加 1
}

// 查询操作：查询字符串 str 在 Trie 树中出现的次数
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 main()
{
    int n;
    scanf("%d", &n); 
    while (n--)
    {
        char op[2]; // 用于存储操作类型
        scanf("%s%s", op, str); // 输入操作类型和字符串
        if (*op == 'I') insert(str); 
        else printf("%d\n", query(str)); 
    }

    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010;      // 数组的最大长度
const int M = 3100010;     // Trie 树的最大节点数
int n;                     // 数组的长度
int a[N];                  // 存储输入的数组
int son[M][2];             // Trie 树的存储结构，son[p][0/1] 表示节点 p 的 0/1 子节点
int idx;                   // 当前 Trie 树中节点的编号，从 1 开始分配

// 插入操作：将整数 x 的二进制表示插入到 Trie 树中
void insert(int x)
{
    int p = 0; // 从根节点开始
    for (int i = 30; i >= 0; i--) // 从最高位到最低位遍历 x 的二进制位
    {
        int& s = son[p][x >> i & 1]; // 获取当前二进制位（0 或 1）对应的子节点
        if (!s) s = ++idx; // 如果子节点不存在，则创建新节点
        p = s; // 移动到子节点
    }
}

// 查询操作：在 Trie 树中查找与 x 异或结果最大的值
int search(int x)
{
    int p = 0, res = 0; // 从根节点开始，res 用于存储异或结果
    for (int i = 30; i >= 0; i--) // 从最高位到最低位遍历 x 的二进制位
    {
        int s = x >> i & 1; // 获取当前二进制位（0 或 1）
        if (son[p][!s]) // 如果存在与当前位相反的节点
        {
            res += 1 << i; // 将当前位的值加到结果中
            p = son[p][!s]; // 移动到相反的节点
        }
        else p = son[p][s]; // 否则，移动到相同的节点
    }
    return res; // 返回最大异或结果
}

int main()
{
    scanf("%d", &n); // 输入数组的长度
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]); // 输入数组的每个元素
        insert(a[i]); // 将当前元素插入到 Trie 树中
    }

    int res = 0; // 用于存储最大异或结果
    for (int i = 0; i < n; i++) res = max(res, search(a[i])); // 对每个元素查询最大异或结果

    printf("%d\n", res); // 输出最大异或结果
    return 0;
}

const int N = 100010;      // 数组的最大长度
const int M = 3100010;     // Trie 树的最大节点数

for (int i = 30; i >= 0; i--) // 从最高位到最低位遍历 x 的二进制位

00000000 00000000 00000000 00000101

res += 1 << i; // 将当前位的值加到结果中

#include <iostream>
using namespace std;

const int N = 100010; // 定义数组的最大长度
int p[N]; // 并查集的父节点数组，p[x] 表示 x 的父节点
int n, m; // n 表示元素的数量，m 表示操作的数量

// 查找操作：找到 x 的根节点，并进行路径压缩
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]); // 如果 x 不是根节点，递归找到根节点，并进行路径压缩
    return p[x]; // 返回 x 的根节点
}

int main()
{
    scanf("%d%d", &n, &m); 

    // 初始化并查集，每个元素的父节点指向自己
    for (int i = 1; i <= n; i++) p[i] = i;

    while (m--)
    {
        char op[2]; // 用于存储操作类型
        int a, b; // 操作涉及的两个元素
        scanf("%s%d%d", op, &a, &b); // 输入操作类型和元素

        if (*op == 'M') // 如果是合并操作
        {
            p[find(a)] = find(b); // 将 a 的根节点的父节点设置为 b 的根节点
        }
        else // 如果是查询操作
        {
            if (find(a) == find(b)) puts("Yes"); // 如果 a 和 b 的根节点相同，输出 "Yes"
            else puts("No"); // 否则，输出 "No"
        }
    }

    return 0;
}

for (int i = 1; i <= n; i++) p[i] = i;

p = [1, 2, 3, 4, 5]

// 查找操作：找到 x 的根节点，并进行路径压缩
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]); // 如果 x 不是根节点，递归找到根节点，并进行路径压缩
    return p[x]; // 返回 x 的根节点
}

p[1] = 1
p[2] = 1
p[3] = 2
p[4] = 3

p[1] = 1
p[2] = 1
p[3] = 1
p[4] = 1

#include <iostream>
using namespace std;

const int N = 100010; // 定义数组的最大长度
int n, m;             // n 表示元素的数量，m 表示操作的数量
int p[N];             // 并查集的父节点数组，p[x] 表示 x 的父节点
int cnt[N];           // 记录每个集合的大小，cnt[x] 表示以 x 为根节点的集合的大小

// 查找操作：找到 x 的根节点，并进行路径压缩
int find(int x)
{
	if (p[x] != x) p[x] = find(p[x]); // 如果 x 不是根节点，递归找到根节点，并进行路径压缩
	return p[x]; // 返回 x 的根节点
}

int main()
{
	cin >> n >> m; // 输入元素的数量和操作的数量

	// 初始化并查集
	for (int i = 1; i <= n; i++)
	{
		p[i] = i; // 每个元素的父节点指向自己
		cnt[i] = 1; // 每个集合的大小初始化为 1
	}

	while (m--)
	{
		string op; // 用于存储操作类型
		int a, b;  // 操作涉及的元素
		cin >> op; // 输入操作类型


		if (op == "C") // 如果是合并操作
		{
			cin >> a >> b; // 输入要合并的两个元素
			a = find(a), b = find(b); // 找到 a 和 b 的根节点
			if (a != b) // 如果 a 和 b 不在同一个集合中
			{
				p[a] = b; // 将 a 的根节点的父节点设置为 b 的根节点
				cnt[b] += cnt[a]; // 更新集合的大小
			}
		}

		else if (op == "Q1") // 如果是查询是否在同一集合中的操作
		{
			cin >> a >> b;
			if (find(a) == find(b)) puts("Yes");
			else puts("No");
		}
		else // 如果是查询集合大小的操作
		{
			cin >> a;
			cout << cnt[find(a)] << endl;
		}
	}

	return 0;
}

if (op == "C") // 如果是合并操作
{
	cin >> a >> b; // 输入要合并的两个元素
	a = find(a), b = find(b); // 找到 a 和 b 的根节点
	if (a != b) // 如果 a 和 b 不在同一个集合中
	{
		p[a] = b; // 将 a 的根节点的父节点设置为 b 的根节点
		cnt[b] += cnt[a]; // 更新集合的大小
	}
}

if (ch == "C")
{
	cin >> a >> b;
	if (find(a) != find(b))
	{
		p[find(a)] = find(b);
		cnt[find(b)] += cnt[find(a)];
	}
}

if (op == "C")
{
    cin >> a >> b;
    if (find(a) != find(b)) // 第一次调用 find(a) 和 find(b)
    {
        p[find(a)] = find(b); // 第二次调用 find(a) 和 find(b)
        cnt[find(b)] += cnt[find(a)]; // 第三次调用 find(a) 和 find(b)
    }
}

#include <iostream>
using namespace std;

const int N = 50010; // 定义数组的最大长度
int n, m;       // n 表示动物的数量，m 表示操作的数量
int p[N];       // 并查集的父节点数组，p[x] 表示 x 的父节点
int d[N];       // 距离数组，d[x] 表示 x 到其父节点的距离

// 查找操作：找到 x 的根节点，并进行路径压缩和距离更新
int find(int x)
{
    if (p[x] != x) // 如果 x 不是根节点
    {
        int t = find(p[x]); // 递归找到根节点
        d[x] += d[p[x]];    // 更新 x 到根节点的距离
        p[x] = t;           // 路径压缩，将 x 直接连接到根节点
    }
    return p[x]; // 返回 x 的根节点
}

int main()
{
    scanf("%d%d", &n, &m); 

    // 初始化并查集
    for (int i = 1; i <= n; i++)
    {
        p[i] = i; // 每个动物的父节点指向自己
        d[i] = 0; // 初始距离为 0
    }

    int res = 0; // 记录虚假陈述的数量
    while (m--)
    {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y); // 输入操作类型和两个动物编号

        if (x > n || y > n) // 如果 x 或 y 超出范围，则是虚假陈述
        {
            res++;
        }
        else
        {
            int px = find(x), py = find(y); // 找到 x 和 y 的根节点
            if (t == 1) // 操作类型 1：x 和 y 是同类
            {
                if (px == py && (d[x] - d[y]) % 3 != 0) // 如果 x 和 y 在同一集合中但距离差不为 0，则是虚假陈述
                {
                    res++;
                }
                else if (px != py) // 如果 x 和 y 不在同一集合中，合并它们
                {
                    p[px] = py;          // 将 x 的根节点连接到 y 的根节点
                    d[px] = d[y] - d[x]; // 更新 x 的根节点到 y 的根节点的距离
                }
            }
            else // 操作类型 2：x 吃 y
            {
                if (px == py && (d[x] - d[y] - 1) % 3 != 0) // 如果 x 和 y 在同一集合中但距离差不满足 x 吃 y 的条件，则是虚假陈述
                {
                    res++;
                }
                else if (px != py) // 如果 x 和 y 不在同一集合中，合并它们
                {
                    p[px] = py;              // 将 x 的根节点连接到 y 的根节点
                    d[px] = d[y] + 1 - d[x]; // 更新 x 的根节点到 y 的根节点的距离
                }
            }
        }
    }

    printf("%d\n", res); // 输出虚假陈述的数量
    return 0;
}

d[px] = d[y] - d[x]; // 更新 x 的根节点到 y 的根节点的距离
d[px] = d[y] + 1 - d[x]; // 更新 x 的根节点到 y 的根节点的距离