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).
↵
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).
