Leetcode-Solutions/longestprefixsuffix.py at main · hawkh/Leetcode-Solutions · GitHub

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
# Longest Prefix Suffix
# Given a string, compute the length of the longest proper prefix which is same as the suffix of the given string.


# Input Format

# The input contains a string S, consisting of only lowercase characters.


# Output Format

# Print the length of the longest proper prefix which is the same as a suffix of the given string.


# Constraints

# 1 <= len(S) <= 100


# Example

# Input

# smartintsmart


# Output

# 5


# Explanation


# Self Explanatory

def kmp(s):
    n=len(s)
    lps=[0]*n
    l=0
    i=1
    while i<n:
        if s[i]==s[l]:
            l+=1
            lps[i]=l
            i+=1
        else:
            if l!=0:
                l=lps[l-1]
            else:
                lps[i]=0
                i+=1
    return lps[-1]

s=input().strip()
print(kmp(s))