def strStr(self, haystack, needle):
        """
        KMP algorithm
        :type haystack: str
        :type needle: str
        :param haystack:
        :param needle:
        :return:
        """
        ln = len(needle)
        lh = len(haystack)
        if ln==0:
            return haystack
        if ln==1:
            try:
                index = haystack.index(needle)
                return haystack[index:]
            except ValueError:
                return None

        # construct T
        T = [0 for _ in xrange(ln)]
        T[0] = -1
        T[1] = 0
        pos = 2
        cnd = 0
        while pos<ln:
            if needle[pos-1]==needle[cnd]:  # pos-1 rather than pos
                cnd += 1
                T[pos] = cnd
                pos += 1
            elif T[cnd]!=-1:
                cnd = T[cnd]
            else:
                cnd = 0
                T[pos] = cnd
                pos += 1

        # search
        i = 0
        m = 0
        while lh < m+i:
            if needle[i]==haystack[m+i]:
                i += 1
                if i==ln:
                    return haystack[m:]
            else:
                if T[i]!=-1:
                    m = m+i-T[i]
                    i = T[i]
                else:
                    m += 1
                    i = 0

        return None
dataset/ETHPy150Open algorhythms/LeetCode/028 Implement strStr().py/Solution.strStr/swapped operands of `<`