Advertisement
Guest User

Untitled

a guest
Mar 21st, 2018
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.98 KB | None | 0 0
  1. set = hash set constructed by counting each occurance of W
  2. sum_w = len(W), used to count the total characters needed for an anagram. 0 when substring is an anagram
  3. sum_extra = 0, used to count extra characters not part of the anagram
  4.  
  5. anagram_idxs = empty linked list
  6.  
  7. substring = S [1:len (W)] <- first part of the string
  8. for each character c in W:
  9. if c is in set d
  10. sum -= 1
  11. else:
  12. sum_extra += 1
  13.  
  14.  
  15. if sum == 0 and sum_extra == 0:
  16. then the initial substring is an anagram
  17. anagram_idx.append(1) or 0, depending on if you want index or character location
  18.  
  19.  
  20. ^ up to here we've used up to O(len(W)) time.
  21.  
  22. for i from 2 to len(S) - len(W): <- I might be one off here
  23. missing_character = S[i-1]
  24.  
  25. if missing_character is in set:
  26. sum_w += 1
  27. else:
  28. sum_extra -= 1
  29.  
  30.  
  31. new_character = S[i+len(W)] <- might be one off
  32.  
  33. if new_character is in set:
  34. sum -= 1
  35. else:
  36. sum_extra += 1
  37.  
  38. if sum == 0 and sum_extra == 0:
  39. anagram_idxs.append(i)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement