我们获取由小写字母组成的密码p,并随机打乱其中的字母以获得p′(p′仍然可以等于p(; 生成两个随机字符串,由小写字母 s1 和 s2 组成(这些字符串中的任何一个都可以为空(; 生成的哈希值 h=s1+p′+s2,其中加法是字符串连接。 我们的输入必须为否。的测试用例,
对于每个测试用例,一个密码和一个散列密码(在不同的行中(, 每个测试用例的输出必须为"是"或"否",具体取决于是否可以从给定密码构造给定哈希。
#include<iostream>
#include<vector>
#define forn(i,n) for(int i=0;i<n;i++)
using namespace std;
void solve(string p, string h) {
vector<int> pcnt(26);
int ps = p.size();
int hs = h.size();
forn(j, ps) {
++pcnt[p[j] - 'a'];
forn(j, hs) {
vector<int> hcnt(26);
for (int m = j; m < j+ps; m++) {
++hcnt[h[m] - 'a'];
if (pcnt == hcnt) {
puts ("YES");
return;
}
}
}
}
puts("NO");
}
int main() {
int t;
cin >> t;
forn(i, t) {
string p, h;
cin >> p >> h;
solve(p, h);
}
}
对于输入
1
one
zzonneyy
我的输出是
YES
我不知道为什么。请帮帮我? 这是关于Codeforce的问题的链接。
你的代码段有几个问题。
forn(j, hs)
被使用两次,j
范围难以 理解。(pcnt == hcnt)
条件检查在第一个字符匹配时立即退出- 宏的使用,这是混淆代码。
#define forn(i,n) for(int i=0;i<n;i++)
宏是邪恶的
找到以下应该可以解决您问题的片段,
void solve (string p, string h)
{
std::vector <int> pcnt (26);
int ps = p.size ();
int hs = h.size ();
//To create a finger print for given password
for (int j = 0; j < ps; ++j)
{
++pcnt[p[j] - 'a'];
}
vector <int>hcnt (26);
//Moving frame to check the matching finger print
for (int i = 0; i < hs; ++i)
{
++hcnt[h[i] - 'a'];
if (i - ps >= 0){
--hcnt[h[i - ps] - 'a'];
}
if (pcnt == hcnt){
puts ("YES");
return;
}
}
puts ("NO");
}