Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.
---
## Large code base
```python [10|30|60]
# Knuth-Morris-Pratt (KMP) Algorithm for Pattern Matching
# Function to create the Longest Prefix Suffix (LPS) array
def compute_lps_array(pattern):
length = 0 # length of the previous longest prefix suffix
lps = [0] * len(pattern) # lps[i] is the length of the longest prefix suffix of pattern[0...i]
i = 1 # Start from the second character of the pattern
# Loop to calculate lps[i] for i = 1 to len(pattern) - 1
while i < len(pattern):
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
# Function implementing the KMP algorithm
def kmp_search(text, pattern):
# Get the length of text and pattern
n = len(text)
m = len(pattern)
# Preprocess the pattern to compute the lps array
lps = compute_lps_array(pattern)
i = 0 # index for text[]
j = 0 # index for pattern[]
# List to store the starting indices of pattern matches
match_positions = []
while i < n:
if pattern[j] == text[i]:
i += 1
j += 1
if j == m:
# Pattern found, record the starting index
match_positions.append(i - j)
j = lps[j - 1] # Reset j using the lps array
elif i < n and pattern[j] != text[i]:
# Mismatch after j matches
if j != 0:
j = lps[j - 1]
else:
i += 1
return match_positions
# Example usage
if __name__ == "__main__":
text = "ababcabcabababd"
pattern = "ababd"
result = kmp_search(text, pattern)
if result:
print(f"Pattern found at indices: {result}")
else:
print("Pattern not found in the text.")
```
---
## Single page large image (fit)
![](../img/screen-test-large.jpg)
![](../img/screen-test-large.jpg)
![](../img/screen-test-large.jpg)
![](../img/screen-test-large.jpg)
![](../img/screen-test-large.jpg)
![](../img/screen-test-large.jpg)
![](../img/screen-test-large.jpg)
![](../img/screen-test-large.jpg)
![](../img/screen-test-large.jpg)
---
# The end