Advertisement
satishfrontenddev4

Untitled

Jan 5th, 2024 (edited)
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. You are given two strings, a main string S, and a pattern P. You have to find the starting indices of the anagrams of P in S.
  3.  
  4.  
  5. Anagrams are permutations of a string. For P="abc”, its anagrams are abc,acb,bca,bac,cba,cab.
  6.  
  7.  
  8. Note that indexing starts at 0.
  9.  
  10. Input format
  11. There is one line of input, containing two space-separated strings S and P.
  12.  
  13. Output format
  14. First-line should contain the number of such starting indices.
  15.  
  16. Next line should contain the indices in increasing order separated by a space.
  17.  
  18. Sample Input 1
  19. aaba ab
  20.  
  21. Sample Output 1
  22. 2
  23.  
  24. 1 2
  25.  
  26. Explanation 1
  27. The anagrams of pattern "ab" are “ab” and “ba”. These are present at indices 1 and 2 of the input string “aaba”.
  28.  
  29. Sample Input 2
  30. bacdgabcda abcd
  31.  
  32. Sample Output 2
  33. 3
  34.  
  35. 0 5 6
  36.  
  37. Explanation 2
  38. The anagrams of "abcd" can be seen as “bacd” at index 0, “abcd” at index 5 and “bcda” at index 6.
  39.  
  40. Constraints
  41. 1 <= length(S), length(P) <= 10^6
  42.  
  43. */
  44.  
  45.  
  46. /**
  47.  * @param {string} s
  48.  * @param {string} p
  49.  * @return {number[]}
  50.  */
  51. // sliding window of frequency array: https://www.youtube.com/watch?v=MW4lJ8Y0xXk&t=202s
  52. function findAllAnagramsInAString(s, p) {
  53.   let hash= new Array(26).fill(0);
  54.   let currentWindow=new Array(26).fill(0);
  55.   let ans=[];
  56.   if(p.length>s.length)
  57.   return ans;
  58.   // console.log(getIndex("e"));
  59.   for(let i=0;i<p.length;i++){
  60.     hash[getIndex(p[i])]++;
  61.   }
  62.   // console.log(hash);
  63.   // get first window
  64.   for(let i=0;i<p.length;i++){
  65.     let currentIndex=getIndex(s[i]);
  66.     currentWindow[currentIndex]++;
  67.   }
  68.   if(compare(hash,currentWindow))
  69.     ans.push(0);
  70.   for(let i=p.length;i<s.length;i++){
  71.     let currentIndex=getIndex(s[i]);
  72.     let removedCharacterIndex=getIndex(s[i-p.length]);
  73.     currentWindow[currentIndex]++;
  74.     currentWindow[removedCharacterIndex]--;
  75.     if(compare(hash,currentWindow))
  76.       ans.push(i-p.length+1);
  77.   }
  78.  
  79.  
  80.   return ans;
  81.  
  82. }
  83.  
  84. function main() {
  85.   let [s, p] = readLine().split(" ");
  86.   let result = findAllAnagramsInAString(s, p);
  87.  
  88.   console.log(result.length);
  89.  
  90.   console.log(...result);
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement