I am reading about the KMP substring search algorithm and the examples I find online use an one-dimensional table to build the prefix information table.
I also read the Sedgewick explanation and he used a 2-D array to build the table and explicitly states that the space complexity of KMP is O(RM) where R is the alphabet size and M the pattern size while everywhere else it is stated that the space complexity is just O(M + N) i.e. the text to process and the pattern size itself.
So I am confused on the difference. Are there multiple KMP algorithmic approaches? And do they have different scope? Or what am I missing?
Why is the 2D needed if 1D can solve the substring problem too?
Are there multiple KMP algorithmic approaches with different space complexities? What is the difference?
295 views Asked by Jim At
1
There are 1 answers
Related Questions in STRING
- What does: "char *argv[]" mean?
- User input sanitization program, which takes a specific amount of arguments and passes the execution to a bash script
- JSON Body is Not Passing Certain Strings
- Regex to match repeated substring in Google Sheets
- Find the sum of the numbers in the sequence
- Hello, how can I use a block parameter of withstyle parameter when we create a annotated string in jetpackpack compose
- How to convert an HTML string to an escaped one?
- Quintic Number Number Counting Hash Function
- From Buffer("string", "hex) to string JS
- Calling ToString with a nominated format returns Char rather than String
- How to update an already existing array by accessing it by a variable with the exact same name assigned to it
- Why does \b not interpreted as backslash in this regular expression
- Python: why aren’t strings being internalized if they are received from ints by using str()?
- If the element(s) in the first list equal element(s) of the second list, replace with element(s) of the third list
- About Suffix Trees features
Related Questions in ALGORITHM
- MCNP 6 - Doubts about cells
- Given partially sorted array of type x<y => first apperance of x comes before first of y, sort in average O(n)
- What is the algorithm behind math.gcd and why it is faster Euclidean algorithm?
- Purpose of last 2 while loops in the merge algorithm of merge sort sorting technique
- Dots and Boxes with apha-beta pruning
- What is the average and worst-case time complexity of my string searching algorithm?
- Building a School Schedule Generator
- TC problem 5-2:how to calculate the probability of the indicator random variable?
- LCA of a binary tree implemented in Python
- Identify the checksum algorithm
- Algorithm for finding a subset of nodes in a weighted connected graph such that the distance between any pair nodes are under a postive number?
- Creating an efficent and time-saving algorithm to find difference between greater than and lesser than combination
- Algorithm to find neighbours of point by distance with no repeats
- Asking code suggestions about data structure and algorithm
- Heap sort with multithreading
Related Questions in SUBSTRING
- Algorithm for finding the largest common substring for n strings using Rabin-Karp function
- Unable to download CSV file from web URL with runtime using python
- Is there any possible way to remove the 1st character of a String using O(1) time complexity in C++?
- Split string based on delimiter into specific substrings in python stored in multiple columns
- Can you replace a substring from a regex match?
- Check Groovy string if it matches dynamically changing substring
- Lookup every character in string and replace with character from another string
- How to make pattern matching efficient for large text datasets
- SQL - Select only records where field contains either a given string explicitly OR or a range of strings within which given string falls
- Word Count in C
- Dynamic starting position in substring and dynamic length
- split string in powershell using delimiter
- Pandas - find all Rows where special Columns contain a part of text
- Searching into an array of long strings specific things. Then save it on a JSON Object
- Substring issue when combined with map or reduce. Am I doing something wrong?
Related Questions in SPACE-COMPLEXITY
- How Fast Does MongoDB Indices Grow in Size?
- Time Complexity of "in" keyword in python when using a list? Leetcode
- lru_cache vs dynamic programming, stackoverflow with one but not with the other?
- Space Complexity of a Recursion Function Involving Additional Self-Contained Auxiliary Space
- Reducing Memory on Binary Search Tree Insertion
- Subtree of Another Tree Complexity Analysis
- Complexity of np.argsort()
- Complexity of std::inplace_merge
- How to find time and space complexity for this js code?
- Space Complexity of flattening 2d array
- How can i improve time complexity of my python code?
- The theoretical complexity of Tries and the distances of Levenshtein to suggest similar words
- Does overwriting an existing array with a new array cost extra time or memory in the context of complexity analysis?
- Auxiliary Space Complexity of Dictionaries whose Keys are Iterables of Variable Size
- Time and Auxiliary Space Complexities of .values(), .items(), .keys()
Related Questions in KNUTH-MORRIS-PRATT
- KMP Skip Table not producing the correct output
- Find the list of starting indexes of occurring of a string in another string in O(N) time complexity
- String period in linear time
- C++ String Comperison - Why Brute Force alg, works faster than my Knuth–Morris–Pratt alg - I know there must a mistake but I don't know were
- How to Implemented Knutt Morris Pratt Algorithm in Laravel?
- Better understanding and comparison of Boyer-Moore and KMP algorithm
- Confused with kmp algorithm
- Why do we take value from the already constructed array in KMP algorithmn when moving back when there is a mismatch , instead of starting from first?
- KMP algorithm with blank letter in pattern
- Leetcode 459 proof for KMP
- What is the best & worst time complexity Of KMP algorithm
- PROLOG: How can I create a KMP algorithm in prolog?
- Knuth-Morris-Pratt algorithm in Scheme
- Are there multiple KMP algorithmic approaches with different space complexities? What is the difference?
- Time complexity of LPS calculation of KMP
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
Popular Tags
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
I guess Sedgewick wanted to demonstrate a variant of KMP that constructs a deterministic finite automaton in the standard sense of that term. It's a weird choice that (as you observe) bloats the running time, but maybe there was a compelling pedagogical reason that I don't appreciate (then again my PhD was on algorithms, so...). I'd find another description that follows the original more closely.