Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- set = hash set constructed by counting each occurance of W
- sum_w = len(W), used to count the total characters needed for an anagram. 0 when substring is an anagram
- sum_extra = 0, used to count extra characters not part of the anagram
- anagram_idxs = empty linked list
- substring = S [1:len (W)] <- first part of the string
- for each character c in W:
- if c is in set d
- sum -= 1
- else:
- sum_extra += 1
- if sum == 0 and sum_extra == 0:
- then the initial substring is an anagram
- anagram_idx.append(1) or 0, depending on if you want index or character location
- ^ up to here we've used up to O(len(W)) time.
- for i from 2 to len(S) - len(W): <- I might be one off here
- missing_character = S[i-1]
- if missing_character is in set:
- sum_w += 1
- else:
- sum_extra -= 1
- new_character = S[i+len(W)] <- might be one off
- if new_character is in set:
- sum -= 1
- else:
- sum_extra += 1
- if sum == 0 and sum_extra == 0:
- anagram_idxs.append(i)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement