Output of my solve(string a, string b) does not match expected output in Shuffle Hashing

Question

We take the password p, consisting of lowercase letters, and shuffle the letters randomly in it to obtain p′ (p′ can still be equal to p); generate two random strings, consisting of lowercase letters, s1 and s2 (any of these strings can be empty); the resulting hash h=s1+p′+s2, where addition is string concatenation. Our input must be no. of testcases,

for each test case, a password and a hashed password(in different lines), output for each test case must be either "YES" or "NO" depending on whether or not the given hash could be constructed out of the given password.

#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);
    }
}

for the input

1
one
zzonneyy

my output is

YES

I'm unable to figure out why.please help me out? here's the link to the question on codeforces.

Did you debug step-wise? – Scheff's Cat Dec 24 '19 at 07:04 — Scheff's Cat, Dec 24 '19 at 07:04

score 1 · Accepted Answer · answered Dec 24 '19 at 10:54

There are couple of issues with your piece of code.

forn(j, hs)is being used twice and scope of j is difficult to understand.
(pcnt == hcnt) condition check exits as soon as first character matches
Usage of Macro's which is obfuscate the code. #define forn(i,n) for(int i=0;i<n;i++) Macro's are evil

Find the below snippet that should solve your problem,

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");
}

Output of my solve(string a, string b) does not match expected output in Shuffle Hashing

1 Answers1