FilesExpand file tree

master

/

prefix_function.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

65 lines (45 loc) · 1.59 KB

master

/

prefix_function.py

Copy path

Top

File metadata and controls

• Code
• Blame

65 lines (45 loc) · 1.59 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

"""

https://cp-algorithms.com/string/prefix-function.html

Prefix function Knuth–Morris–Pratt algorithm

Different algorithm than Knuth-Morris-Pratt pattern finding

E.x. Finding longest prefix which is also suffix

Time Complexity: O(n) - where n is the length of the string

"""

def prefix_function(input_string: str) -> list:

"""

For the given string this function computes value for each index(i),

which represents the longest coincidence of prefix and suffix

for given substring (input_str[0...i])

For the value of the first element the algorithm always returns 0

>>> prefix_function("aabcdaabc")

[0, 1, 0, 0, 0, 1, 2, 3, 4]

>>> prefix_function("asdasdad")

[0, 0, 0, 1, 2, 3, 4, 0]

"""

# list for the result values

prefix_result = [0] * len(input_string)

for i in range(1, len(input_string)):

# use last results for better performance - dynamic programming

j = prefix_result[i - 1]

while j > 0 and input_string[i] != input_string[j]:

j = prefix_result[j - 1]

if input_string[i] == input_string[j]:

j += 1

prefix_result[i] = j

return prefix_result

def longest_prefix(input_str: str) -> int:

"""

Prefix-function use case

Finding longest prefix which is suffix as well

>>> longest_prefix("aabcdaabc")

4

>>> longest_prefix("asdasdad")

4

>>> longest_prefix("abcab")

2

"""

# just returning maximum value of the array gives us answer

return max(prefix_function(input_str))

if __name__ == "__main__":

import doctest

doctest.testmod()