SBS

Agenda: Quick Intro Input Output Complexity Algo Logic C++ Code Real-Life use cases Practice Problem Conclusion Sources for further reading Quick Intro The Z-function is a powerful string-matching algorithm used for pattern matching and searching within a given string. Its primary purpose is to find all occurrences of a specified pattern in the text. Definition: Given a string s of length n, the Z-function produces an array Z where Z[i] represents the length of the longest substring starting from s[i] that is also a prefix of s. Input Text(T): The input to the Z-function algorithm is a single string T of length n . Output Z-Array(z): The output of the Z-function algorithm is an array Z of length n where each element Z[i] represents the length of the longest substring starting from the position i in T that matches a prefix of T . Complexity Time: O(n) Space: O(n) Where, n ---> length of input Text....

Agenda: Quick Intro Input Output Complexity Algo Logic Code Real-Life Use Cases Conclusion Sources for further reading 1. Quick Intro The Knuth-Morris-Pratt (KMP) algorithm is a classic string-searching algorithm used to find occurrences of a "pattern" string within a "text" string.  It was devised by Donald Knuth , James H. Morris , and Vaughan Pratt , hence the name KMP .  The key feature of the KMP algorithm is its ability to perform the search efficiently by avoiding unnecessary comparisons . 2. Input The KMP algorithm takes two inputs: Text (T) : The string in which we are searching for a pattern. Pattern (P) : The string we are searching for within the text. 3. Output Indices (I): Starting indices of all occurrences of the pattern in the text. If the pattern is not found, it returns an empty list. 4. Complexity Time Complexity :  O(n + m)   n ---> Length of the text. m ---> Length of the pattern. Sp...

Agenda: Quick Intro Why? Understanding Morris Traversal: The Threaded Binary Tree Advantages Drawbacks Implementation in Python Time & Space Complexity Conclusion Quick Intro Morris Traversal is a clever tree traversal algorithm that allows us to traverse a binary tree in CONSTANT SPACE . (i.e. without recursion or an explicit stack). Why? When dealing with binary trees, traditional traversal methods like In-order, Pre-order, and post-order often require additional space proportional to the height of the tree, primarily for the recursion stack. This space complexity can be a limitation in memory-constrained environments . Understanding Morris Traversal: The Threaded Binary Tree Named after its inventor, Joseph M. Morris, this traversal technique leverages the concept of threading the binary tree . Threading the binary tree means it uses threads or links pointing to ancestor node...