Example Data Table
| Pattern | Failure Function | Use Case |
|---|---|---|
| ABABCABAB | [0, 0, 1, 2, 0, 1, 2, 3, 4] | Classic prefix fallback study |
| AAAA | [0, 1, 2, 3] | Repeated character pattern |
| ABCABD | [0, 0, 0, 1, 2, 0] | Mismatch after partial match |
| AABAACAABAA | [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5] | Longer prefix structure |
Formula Used
The KMP failure function is also called the LPS table. LPS means longest proper prefix that is also a suffix. For each position i, the calculator finds the greatest length k. The prefix pattern[0...k-1] must equal the suffix ending at i.
If pattern[i] equals pattern[len], then len increases by one. The failure value at i becomes len. If the symbols do not match, len falls back to LPS[len - 1]. This fallback continues until a match appears or len becomes zero.
Time complexity is O(n), because every character is processed with controlled fallback movement. Space complexity is O(n), because the table stores one value for every character.
How to Use This Calculator
Enter a pattern in the input box.
Select character mode for normal strings.
Select space or comma mode for token lists.
Choose case sensitivity based on your matching problem.
Choose zero based or one based index display.
Press the calculate button.
Review the result table above the form.
Use the CSV or PDF buttons to save the output.
Advanced Guide to KMP Failure Function
What the Table Means
The KMP failure function is a preprocessing table for pattern matching. It stores how much of a pattern can still be reused after a mismatch. This saves repeated scanning. A simple search may restart many comparisons. KMP avoids that waste. It remembers useful prefix information. Each table value describes a border of a substring. A border is both a prefix and a suffix. It must be proper. So the whole substring does not count.
Why It Is Useful
The table is important in string algorithms. It helps search large text with predictable speed. The text pointer never moves backward. The pattern pointer moves by using stored fallback values. This makes the method efficient. It is helpful for editors, compilers, search tools, and data processing. Students also use it to understand automata ideas. The table shows hidden repetition inside a pattern.
How the Calculation Works
The calculator starts with the first value as zero. Then it scans the pattern from left to right. A length variable tracks the current matching prefix. When symbols match, the length grows. That length becomes the table value. When symbols differ, the calculator does not restart blindly. It falls back to an earlier table value. This is the key idea of KMP.
Reading the Results
A zero value means no useful prefix continues there. A larger value means a repeated prefix exists. For example, a value of three means three starting symbols match the suffix ending at that position. The step table explains each comparison. It also shows fallback changes. This makes debugging easier. It is useful when learning by hand. It also helps verify code.
Practical Notes
Use character mode for normal words, DNA strings, binary strings, and code tokens without spaces. Use token mode when pattern items are separated. Case insensitive mode treats uppercase and lowercase as equal. Export options help store assignments and reports. The CSV file is useful for spreadsheets. The PDF download gives a simple report. Always check the selected index style. It affects display only. It does not change the algorithm.
FAQs
What is a KMP failure function?
It is a table that stores the longest proper prefix which is also a suffix for each pattern position.
Is the failure function the same as LPS?
Yes. Many lessons call it the LPS table. It means longest proper prefix suffix table.
Why does KMP need this table?
KMP uses the table to avoid restarting comparisons after a mismatch. It reuses known pattern structure.
Can I use numbers as pattern tokens?
Yes. Choose comma or space separated token mode, then enter numbers as separate pattern items.
Does case sensitivity affect results?
Yes. Case sensitive mode treats A and a differently. Case insensitive mode treats them as equal.
What does a zero value mean?
It means no proper prefix also works as a suffix at that position.
What is the time complexity?
The preprocessing time is O(n), where n is the pattern length.
Can I export the table?
Yes. Use the CSV button for spreadsheet data or the PDF button for a simple report file.