String Algorithms

String Algorithms

# Reverse string
s[::-1]

# Check palindrome
def is_palindrome(s):
    s = ''.join(c.lower() for c in s if c.isalnum())
    return s == s[::-1]

# Longest palindromic substring -- O(n^2)
def longest_palindrome(s):
    res = ''
    for i in range(len(s)):
        for odd, even in [(i,i),(i,i+1)]:  # expand around centre
            lo, hi = odd, even
            while lo>=0 and hi len(res):
                res = s[lo+1:hi]
    return res

# Anagram check
from collections import Counter
def is_anagram(s, t): return Counter(s)==Counter(t)

# KMP pattern matching -- O(n+m)
def kmp(text, pattern):
    # Build failure function
    m    = len(pattern)
    lps  = [0]*m
    j    = 0
    for i in range(1,m):
        while j and pattern[i]!=pattern[j]: j = lps[j-1]
        if pattern[i]==pattern[j]: j += 1
        lps[i] = j
    # Search
    j = 0
    for i,c in enumerate(text):
        while j and c!=pattern[j]: j = lps[j-1]
        if c==pattern[j]: j += 1
        if j==m: return i-m+1  # found at index
    return -1