过程模拟
这段代码是一个简单的字符串处理程序,它使用字母树(Trie树)来实现插入和查询操作。让我为您模拟一下这个过程:
输入:5
首先,读取n的值,此时 n = 5。
进入循环,读取操作类型和字符串:
输入:I abc
操作类型是’I’,所以执行插入操作,将字符串 “abc” 插入到字母树中。
继续循环,读取下一个操作:
输入:Q abc
操作类型是’Q’,所以执行查询操作,查询字符串 “abc” 是否存在于字母树中。
字母树中存在 “abc”,因此输出 1。
继续循环,读取下一个操作:
输入:Q ab
操作类型是’Q’,所以执行查询操作,查询字符串 “ab” 是否存在于字母树中。
字母树中不存在 “ab”,因此输出 0。
继续循环,读取下一个操作:
输入:I ab
操作类型是’I’,所以执行插入操作,将字符串 “ab” 插入到字母树中。
继续循环,读取最后一个操作:
输入:Q ab
操作类型是’Q’,所以执行查询操作,查询字符串 “ab” 是否存在于字母树中。
字母树中存在 “ab”,因此输出 1。
循环结束,程序完成。
所以,根据给定的输入,程序的输出将是:
1
0
1
C++ 代码
```
include[HTML_REMOVED]
using namespace std;
const int N = 100010; // 定义常量N,表示数组大小
char str[N]; // 定义字符数组str,用于存放输入的字符串
int son[N][26]; // 定义二维数组son,用于表示字母树结构,每个节点有26个可能的子节点
int cnt[N]; // 定义数组cnt,用于存放以当前节点结尾的单词数量
int idx; // 定义变量idx,表示当前使用的节点下标,初始值为0
void insert(char str[])
{
int p = 0; // 初始化变量p,表示当前在字母树中的位置,初始为根节点
for (int i = 0; str[i]; i) // 遍历输入的字符串
{
int u = str[i] - ‘a’; // 计算当前字符在字母表中的位置
if (!son[p][u]) son[p][u] = idx; // 如果当前位置没有对应的子节点,则创建一个新的节点,并更新idx
p = son[p][u]; // 移动到下一个节点
}
cnt[p]++; // 在最终的节点上增加单词计数
}
int query(char str[])
{
int p = 0; // 初始化变量p,表示当前在字母树中的位置,初始为根节点
for (int i = 0; str[i]; i++) // 遍历输入的字符串
{
int u = str[i] - ‘a’; // 计算当前字符在字母表中的位置
if (!son[p][u]) // 如果当前位置没有对应的子节点
{
return 0; // 返回0,表示没有找到该单词
}
p = son[p][u]; // 移动到下一个节点
}
return cnt[p]; // 返回以当前节点结尾的单词数量
}
int main()
{
int n;
scanf(“%d”, &n); // 读取n的值
while (n–)
{
char op[2]; // 定义字符数组op,用于存放操作类型
scanf(“%s%s”, op, str); // 读取操作类型和字符串
if (op[0] == ‘I’) insert(str); // 如果操作类型是’I’,则执行插入操作
else printf(“%d\n”, query(str)); // 如果操作类型是’Q’,则执行查询操作,并输出结果
}
return 0;
}
java代码:
’‘’
import java.util.Scanner;
public class Main {
static final int N = 100010;
static char[][] son = new char[N][26];
static int[] cnt = new int[N];
static int idx = 0;
static void insert(String str) {
int p = 0;
for (int i = 0; i < str.length(); i++) {
int u = str.charAt(i) - 'a';
if (son[p][u] == 0) {
son[p][u] = (char) ('a' + (++idx));
}
p = son[p][u];
//首先,它通过 (char) ('a' + (++idx)) 计算出一个新的节点的下标,
//并将其赋值给 son[p][u],以表示字符 u 对应的子节点。这里使用 ++idx 来获取一个唯一的节点下标。
//然后,将 p 更新为新创建的子节点的下标,以便在下一次循环中处理下一个字符
}
cnt[p]++;
}
static int query(String str) {
int p = 0;
for (int i = 0; i < str.length(); i++) {
int u = str.charAt(i) - 'a';
if (son[p][u] == 0) {
return 0;
}
p = son[p][u];
}
return cnt[p];
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
while (n-- > 0) {
String op = scanner.next();
String str = scanner.next();
if (op.equals("I")) {
insert(str);
} else {
System.out.println(query(str));
}
}
scanner.close();
}
}