Rabin-Karp Algorithm

Random thought: it turns out that Rabin-Karp is based on quite simple things - first, knowing the hash function and, second, understanding that the previous hash of the substring could be used to calculate the next one (when including next symbol) in O(1) instead of calculating the next hash anew in O(n).

Comments

Post a Comment

Popular posts from this blog

DXGI fast screen capture

Task at hand was capturing desktop or monitor contents under Windows really fast. Actually, the faster is better because the real contents of the buffer I am writing to will be displayed/rendered in real time. There are several options of screen capture in Windows. The oldest and the easiest one is using GDI. The minus of it is that it's really slow. The second way of performing capture is DirectX Graphics Infrastructure - you command video card to store the whole screen or one/several monitors's contents inside separate part of its memory (surface). After that, you can either command video card to draw it somewhere else (for example, on texture). Or lock this surface and copy its contents to the main memory. Looks a lot more promising, huh? Of course I chose the DXGI way! To keep the actual DXGI-based implementation away from the main sources, I had created DXGIManager object incapsulating the actual capture stuff and opened up only a few basic methods: HRESULT SetCapt...
Read more

Kubuntu 16.04 and Dell Inspiron 7559

Problem: Recently, I was more and more than fascinated by development convenience under the modern Linux distributions, not in the last place because I started to use Ubuntu on daily basis at work. So I decided to try Linux on my home laptop (Dell 7559). Options were: Install it as a virtual machine Dual boot At first, I tried installing Ubuntu/Kubuntu inside VM but it turned out to be a bad decision because of the 4K display of the laptop - interface was too slow for the normal usage. I tried both VMWare Player 12 and VirtualBox, tried even setting the scaling of the display in the latter to 200% so Ubuntu will have only 1080p virtual screen but it lagged even more. No go. Then I decided to try the dual boot approach. Luckily, when moving my system to SSD, I had to shrink the Windows partition and had about 200 Gb of the free place in the end of the disk where I decided to put the Kubuntu 16.04. Why Kubuntu? When trying out Ubuntu and Kubuntu inside VM, I found the scal...
Read more

Mindset

Carol Dweck's book has simple thought: growth vs fixed mindset is the core of learning process, how we face the challenges. Because of simplicity, this thought really feels true. The corollaries of the mindset are huge. Literally - the general path in life we choose when using one mindset or the other. As a father, chapter about praising effort and not the talent in the children is especially helpful (done something very fast and without effort? Then it was too easy for you, let's do something challenging!)
Read more