用C语言并查集实现给定一个字符串s和两个字符c1,c2,均保证只含有小写因为字母,请求出有多少个s的字串,符合以c1开头,以c2结束,输入要求为第一行有一个整数n,n的范围为1到10的5次方,和两个字符c1,c2,代表字符串的长度和起始/末尾字符。第二行有一个字符串s,长度为n,仅包含小写字母。
时间: 2023-06-11 21:04:11 浏览: 146
C语言程序设计-输入一个字符串,过滤此串,只保留串中的字母字符,并统计新生成串中包含的字母个数;
5星 · 资源好评率100%
非常感谢您的提问。根据您的要求,我可以帮您实现给定一个字符串s和两个字符c1,c2,均保证只含有小写字母,求出有多少个s的字串,符合以c1开头,以c2结束的问题。以下是C语言并查集实现的代码:
```
#include <stdio.h>
#include <string.h>
#define MAXN 100005
int n;
char s[MAXN];
int parent[MAXN], size[MAXN];
void init() {
for (int i = 0; i < n; ++i) {
parent[i] = i;
size[i] = 1;
}
}
int find(int x) {
if (parent[x] == x) {
return x;
}
return parent[x] = find(parent[x]);
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) {
parent[fx] = fy;
size[fy] += size[fx];
}
}
int main() {
int c1, c2;
scanf("%d %d %d %s", &n, &c1, &c2, s);
init();
int ans = 0;
for (int i = 0; i < n; ++i) {
if (s[i]-'a'+1 == c1) {
for (int j = i + 1; j < n; ++j) {
if (s[j]-'a'+1 == c2) {
merge(i, j);
++ans;
}
}
}
}
printf("%d\n", ans);
return 0;
}
```
希望这个回答能够解决您的问题。如果您有任何其他问题,请随时提问。
阅读全文