cyga

bold strings

Sep 18th, 2021
557
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class PolyHash():
  2.     def __init__(self, seq: List[int], prime=37, rem=10**9+7):
  3.         n = len(seq)
  4.         self.rem = rem
  5.         self.hashes = [0]*(n+1)
  6.         self.pows = [1]*(n+1)
  7.         for i in range(1, n+1):
  8.             self.pows[i] = self.pows[i-1]*prime % rem
  9.             self.hashes[i] = (self.hashes[i-1]*prime + seq[i-1]) % rem
  10.  
  11.     def hash(self, l: int, r: int):
  12.         ''' [l, r) '''
  13.         return (self.hashes[r] - (self.hashes[l]*self.pows[r-l]) % self.rem) % self.rem
  14.    
  15. def string_hasher(s: string) -> PolyHash:
  16.     return PolyHash([ord(ch)-ord('a') for ch in s])
  17.  
  18. def calc_word_hashes(words: List[str]) -> List[int]:
  19.     word_hashes = [None]*len(words)
  20.     for i, word in enumerate(words):
  21.         word_hasher = string_hasher(word)
  22.         word_hashes[i] = word_hasher.hash(0, len(word))
  23.     return word_hashes
  24.    
  25. def scanline(bolds: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
  26.     START, END = 0, 1
  27.     pois = [(start, START) for start, _ in bolds] + [(end, END) for _, end in bolds]
  28.     pois.sort()
  29.    
  30.     n_opened = 0
  31.     b_start = None
  32.     res = []
  33.     for x, tip in pois:
  34.         if tip == START:
  35.             if n_opened == 0:
  36.                 b_start = x
  37.             n_opened += 1
  38.         else:
  39.             n_opened -= 1
  40.             if n_opened == 0:
  41.                 res.append((b_start, x))
  42.                
  43.     return res
  44.    
  45. class Solution:
  46.     def boldWords(self, words: List[str], s: str) -> str:
  47.         word_hashes = calc_word_hashes(words)
  48.         s_hasher = string_hasher(s)
  49.         bolds = []
  50.         for i in range(1, len(s)+1):
  51.             for j, h in enumerate(word_hashes):
  52.                 if i >= len(words[j]):
  53.                     if s_hasher.hash(i-len(words[j]), i) == h:
  54.                         bolds.append((i-len(words[j]), i))
  55.                        
  56.         bolds = scanline(bolds)
  57.         res = []
  58.         j, k = 0, 0
  59.         for i in range(len(s)+1):
  60.             if j < len(bolds) and bolds[j][k] == i:
  61.                 if k == 0:
  62.                     res.append("<b>")
  63.                     k += 1
  64.                 else:
  65.                     res.append("</b>")
  66.                     k = 0
  67.                     j += 1
  68.                
  69.             if i < len(s):
  70.                 res.append(s[i])
  71.                        
  72.         return ''.join(res)
RAW Paste Data