Skip to content

Instantly share code, notes, and snippets.

@RaphaelAslanian
RaphaelAslanian / powers.py
Created January 14, 2018 11:00
Last two digits of x^n
def last_digits_power(n):
"""Display the last two digits of n to the power of n"""
result = last_digits(n, n)
result_tens, result_units = result // 10, result % 10
print("First digit: {}, Second digit: {}".format(result_tens, result_units))
return result_tens, result_units
def last_digits(base, exponent):
"""
@RaphaelAslanian
RaphaelAslanian / KMP_algo.py
Last active November 26, 2018 02:19
Implementation of the Knuth-Morris-Pratt algorithm
"""
This module contains an implementation of the Knuth-Morris-Pratt algorithm allowing to look for sequence matching.
For example if you want to find the sequence [1, 2, 3] in [2, 3, 1, 2, 3, 5, 6], you could do:
find_sequence([2, 3, 1, 2, 3, 5, 6], [1, 2, 3])
This algorithm is especially interesting in case of many partial matches. Otherwise, you could simply use a brute
force search with correct performances.
The main function to use here is find_sequence which actually performs the KMP algorithm.