Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
KMP algorithm implementation solution in Speedy category for Count Substring Occurrences by vyacheslavandrosiuk
def compute_prefix_func(pattern: str) -> list:
m = len(pattern)
prefix_func = [0] * m
j = 0
for i in range(1, m):
if pattern[i] != pattern[j]:
if j == 0:
prefix_func[i] = 0
else:
j = prefix_func[j - 1]
elif pattern[i] == pattern[j]:
prefix_func[i] = j + 1
j += 1
return prefix_func
def count_occurrences(main_str: str, sub_str: str) -> int:
main_str = main_str.lower()
sub_str = sub_str.lower()
computed_prefix = compute_prefix_func(sub_str)
count = 0
m = len(sub_str)
n = len(main_str)
i = 0
j = 0
while i < n:
if main_str[i] == sub_str[j]:
i += 1
j += 1
if j == m:
count += 1
j = computed_prefix[j - 1]
else:
if j > 0:
j = computed_prefix[j - 1]
else:
i += 1
return count
print("Example:")
print(count_occurrences("hello world hello", "hello"))
# These "asserts" are used for self-checking
assert count_occurrences("hello world hello", "hello") == 2
assert count_occurrences("Hello World hello", "hello") == 2
assert count_occurrences("hello", "world") == 0
assert count_occurrences("hello world hello world hello", "world") == 2
assert count_occurrences("HELLO", "hello") == 1
assert count_occurrences("appleappleapple", "appleapple") == 2
assert count_occurrences("HELLO WORLD", "WORLD") == 1
assert count_occurrences("hello world hello", "o w") == 1
assert count_occurrences("apple apple apple", "apple") == 3
assert count_occurrences("apple Apple apple", "apple") == 3
assert count_occurrences("apple", "APPLE") == 1
print("The mission is done! Click 'Check Solution' to earn rewards!")
April 6, 2025
Comments:
