A string matching problem
Разница между en2 и en3, 68 символ(ов) изменены
My IP has been banned from luogu for some reason, so I'm asking this question on CF.↵

Question:↵

If string S and T with same length has $k$ or less different characters, we say S matches T,↵

then if A and B are given, how to find every substring of A that matches B?↵

My English is poor, so there would be some grammar mistakes, but I think u can understand what I mean.↵

I don't need trivial solutions such as $O(n^2)$ (brute) or $O(nk\log n)$ (hash)
 or $O(\dfrac{n^2\Sigma}w)$ (bitset, probably not faster than brute).

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский 5k_sync_closer 2024-09-18 16:19:14 68 Tiny change: 'dfrac{n^2\sigma}w)$ (' -> 'dfrac{n^2\Sigma}w)$ ('
en2 Английский 5k_sync_closer 2024-09-18 16:15:16 84
en1 Английский 5k_sync_closer 2024-09-18 16:13:28 403 Initial revision (published)