社区讨论

为什么样例第一个总是输出4,求调

P10470前缀统计参与者 2已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@lyjd2mq1
此快照首次捕获于
2024/07/13 08:01
2 年前
此快照最后确认于
2024/07/13 08:24
2 年前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;

int t, n, q;
struct node{
	int son[100];
	int cnt;
} a[100005];
int get(char ch)
{
	if (ch >= 'A' && ch <= 'Z')
	{
		return ch - 'A' + 27;
	}
	else if (ch >= 'a' && ch <= 'z')
	{
		return ch - 'a' + 1;
	}
	return ch - '0' + 53;
}
void insert(string s)
{
	int len = s.size(), now = 1, cnt = 1;
	for (int i = 0; i < len; i++)
	{
//		cout << now << ' ';
		int num = get(s[i]);
		if (a[now].son[num] == 0)
		{
			a[now].son[num] = ++cnt;
		}
		now = a[now].son[num];
		if (i == len - 1)
		{
			a[now].cnt++;
		}
	}
//	cout << endl;
	return ;
}
void find(string s)
{
	int len = s.size(), now = 1, ans = 0;
	for (int i = 0; i < len; i++)
	{
		int num = get(s[i]);
		if (a[now].son[num] == 0)
		{
			cout << ans << endl;
			return ;
		}
		now = a[now].son[num];
		ans += a[now].cnt;
//		cout << ans << ' ';
	}
	cout << ans << endl;
	return ;
}
/*void clearing(int x)
{
	for (int i = 1; i <= x; i++)
	{
		for (int j = 0; j <= 62; j++)
		{
			a[i].son[j] = 0;
		}
		a[i].cnt = 0;
	}
}
*/
signed main()
{
	ios::sync_with_stdio();
	cin.tie(0);cout.tie(0);
	t = 1;
//	cin >> t;
	while (t--)
	{
		int n, q;
		cin >> n >> q;
//		clearing(id);
		for (int i = 0; i < n; i++)
		{
			string s;
			cin >> s;
			insert(s);
		}
		while (q--)
		{
			string s;
			cin >> s;
			find(s);
		}
	}
	return 0;
}

回复

5 条回复,欢迎继续交流。

正在加载回复...