关注
在做题的始终是在想将所有的输出结果保存了然后最后一次性输出,结果始终输出不了。现在就直接将输出改为cout输出了。现在虽然本地可以AC了,但是就想问问大佬们,我对多case的处理是否正确。 #include<iostream>
#include<string>
#include<vector>
using namespace std;
bool isMatch(const string &dict, const string &example);
vector<int> getNext(const string &needle, int m, vector<int> next);
int main()
{
while (cin) //此处是否正确?
{
int N;
cin >> N;
vector<string> dict(N, "");
for (int i = 0;i<N;i++)
{
cin >> dict[i];
}
int M;
cin >> M;
vector<string> example(M, "");
for (int i = 0;i<M;i++)
{
cin >> example[i];
}
for (int i = 0;i<M;i++)
{
int count = 0;
for (int j = 0;j<N;j++)
{
if (isMatch(dict[j], example[i]))
{
count++;
}
}
cout << count << endl; //输出
}
}
return 0;
}
//KMP匹配算法
bool isMatch(const string &dict, const string &example)
{
int n = dict.size(), i = 0;
int m = example.size(), j = 0;
if (m>n) return false;
if (n == 0 || m == 0) return true;
vector<int> next(m);
next = getNext(example, m, next);
while (j<m&&i<n)
{
if ((0>j) || dict[i] == example[j])
{
i++;
j++;
}
else
{
j = next[j];
}
}
return j == m ? true : false;
}
vector<int> getNext(const string &needle, int m, vector<int> next)
{
int t = -1;
next[0] = -1;
int j = 0;
while (j<m - 1)
{
if (0>t || needle[j] == needle[t])
{
j++;
t++;
next[j] = (needle[j] != needle[t] ? t : next[t]);
}
else
t = next[t];
}
return next;
}
查看原帖
点赞 1
相关推荐
点赞 评论 收藏
分享
牛客热帖
正在热议
# 25届秋招总结 #
473144次浏览 4838人参与
# 职场情商大赛 #
2009次浏览 35人参与
# 地方国企笔面经互助 #
8974次浏览 19人参与
# 晒一晒我的offer #
10046161次浏览 106476人参与
# 今年形式下双非本找得到工作吗 #
52813次浏览 487人参与
# 如何排解工作中的焦虑 #
75305次浏览 1068人参与
# 同bg的你秋招战况如何? #
94669次浏览 729人参与
# 怎么面对正在吵架的两个同事 #
8239次浏览 70人参与
# 第一份工作应该选择高薪还是大平台 #
93088次浏览 605人参与
# 面试体验感最好的是哪家? #
99347次浏览 1018人参与
# 找工作时遇到的神仙HR #
570282次浏览 3902人参与
# Offer比较,你最看重什么? #
110117次浏览 778人参与
# 你觉得比亚迪今年还有春招吗? #
157346次浏览 950人参与
# 面试被问第一学历差时该怎么回答 #
80552次浏览 517人参与
# 比亚迪秋招开啦,你打算投递吗? #
37672次浏览 337人参与
# 实习,投递多份简历没人回复怎么办 #
2470243次浏览 34978人参与
# 求职你最看重什么? #
17996次浏览 125人参与
# 你投了多少份简历了? #
69378次浏览 822人参与
# 机械人怎么评价今年的华为 #
159895次浏览 1364人参与
# 国企/银行/研究所公司爆料 #
92834次浏览 424人参与