Krótko, konkretnie, technicznie — notatki z praktyki.
Wprowadzam algorytm Knuth–Morris–Pratt do wyszukiwania wzorca w tekście: intuicja stojąca za funkcją prefix/suffix, konstrukcja tablicy „lps” oraz analiza złożoności. Omawiam też, kiedy KMP ma przewagę nad naiwnym porównywaniem znak po znaku.
Na prostym przykładzie pokazuję klasyczny, naiwny algorytm wyszukiwania podciągu w tekście oraz szczegółowo omawiam jego ograniczenia: złożoność czasową, powtarzane porównania i sytuacje, w których to podejście zaczyna być problematyczne.
MD5 implementacja w C++ - prosta implementacja algorytmu MD5 w języku C++.
Wprowadzam pojęcie programowania dynamicznego i pokazuję, jak zastosować go do rozwiązania problemu Longest Common Subsequence. Przedstawiam koncepcję rozdzielania problemu na mniejsze części i wykorzystywania wyników tych części do uzyskania rozwiązania głównego. Na przykładzie ilustruję, jak wykorzystać wiedzę o najdłuższych wspólnych podciągach do obliczenia najdłuższego wspólnego podciągu dla dwoch ciągów znaków.
Wprowadzam pojęcie programowania dynamicznego i pokazuję, jak zastosować go do rozwiązania problemu Longest Increasing Sequence. Przedstawiam koncepcję rozdzielania problemu na mniejsze części i wykorzystywania wyników tych części do uzyskania rozwiązania głównego. Na przykładzie ilustruję, jak wykorzystać wiedzę o najdłuższych podciągach do obliczenia najdłuższego podciągu po dodaniu nowego elementu do ciągu.