串的模式匹配算法(求子串位置的定位函数Index(S,T,pos))

串的模式匹配算法主要有朴素算法、KMP算法、Boyer-Moore算法等。其中，KMP算法是一种比较高效的算法，可以在O(n+m)的时间内完成匹配操作。下面是KMP算法的定位函数Index(S,T,pos)的实现过程：

def getNext(T):
    """
    计算模式串T的next数组
    """
    n = len(T)
    next = [0] * n
    i, j = 1, 0
    while i < n:
        if j == 0 or T[i] == T[j]:
            i += 1
            j += 1
            next[i-1] = j
        else:
            j = next[j-1]
    return next

def Index(S, T, pos):
    """
    在串S中从pos位置开始查找模式串T的位置
    """
    n, m = len(S), len(T)
    if pos <= 0 or pos > n:
        return -1
    next = getNext(T)
    i, j = pos-1, 0
    while i < n and j < m:
        if j == 0 or S[i] == T[j]:
            i += 1
            j += 1
        else:
            j = next[j-1]
    if j == m:
        return i - m
    else:
        return -1

其中，getNext函数用于计算模式串T的next数组，Index函数用于在串S中从pos位置开始查找模式串T的位置。具体算法流程和实现细节可以参考注释。