上海计算机学会2024年3月月赛C++乙组T3精确匹配
发布时间
阅读量：
阅读量
精确匹配
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定一个字符串称之为模式 p，再给定一个字符串称之为文本 t。请计算 p 是否可以成为 t 的子串，输出 t 有多少种不同位置的子串恰好等于 p。
输入格式
- 第一行：单个字符串表示 p
- 第二行：单个字符串表示 t
- 保证 p 与 t 仅由小写字母构成。
输出格式
- 单个整数：表示答案
数据范围
- 30% 的数据，1≤∣t∣≤100
- 60% 的数据，1≤∣t∣≤10000
- 1000% 的数据，1≤∣p∣≤∣t∣≤300,000
样例数据
输入:
5
10 20 30 40 50
输出:
90
解析：KMP算法，详见代码：
#include<iostream>
#include<string>
using namespace std;
int n, m;
int ne[300010];
string p, t;
int ans = 0;
//这个函数对字符串s进行预处理得到next数组
void get_Next(string s, int ne[]) {
int j = 0;
ne[0] = 0; //初始化
//i指针指向的是后缀末尾，j指针指向的是前缀末尾
for (int i = 1; i < s.size(); i++) {
//前后缀不相同，去找j前一位的最长相等前后缀
while (j > 0 && s[i] != s[j]) j = ne[j - 1];
if (s[i] == s[j]) j++; //前后缀相同，j指针后移
ne[i] = j; //更新next数组
}
}
int main() {
cin >> p >> t;
m = t.length();
n = p.length();
get_Next(p, ne);
for (int i = 0, j = 0; i < m; i++) {
while (j > 0 && t[i] != p[j]) j = ne[j - 1];
if (t[i] == p[j]) j++;
if (j == n) {
ans++;
j = ne[j - 1];
}
}
cout << ans;
return 0;
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~