字符串匹配

void Next(char *P){
    int m = strlen(P);//模式串P的长度
    N[0] = 0;//位置0处的部分匹配串长度为0
    int i = 1; j = 0;//初始化比较位置
    while(i < m){
        if(P[i] == P[j]) {//已经匹配了j＋1个字符
            N[i] = j+1;//部分匹配串长度加一
            i++; j++;//比较位置各进一
        }
        else if(j > 0) j = N[j-1];//移动：用部分匹配串对齐
        else { N[i++] = 0;}//j在串头时部分匹配串长度为0
    }
}
int KMP_match(char *T, char *P){
    int n = strlen(T), m = strlen(P); //目标串和模式串长度
    int i=0, j=0; next(P);//预处理函数
    while (i<n) {
        if (T[i]==P[j]) {//已经匹配j＋1个字符
            if (j == m-1) return i-j;//匹配成功，返回匹配位置
            else { i++; j++; }//比较下一个位置
        }
        else {
            if (j>0) j = N[j-1];//匹配不成功，移动到部分匹配串
            else i++;//失配
        }
    }
    return -1;//匹配失败
}

def strStr(self, haystack, needle):
    """
    :type haystack: str
    :type needle: str
    :rtype: int
    """
    N = self.next(needle)
    n, m = len(haystack), len(needle)
    if m==0:
        return 0
    i = 0
    j = 0
    while i<n:
        if haystack[i]==needle[j]:
            if j==m-1:
                return i-j
            else:
                i　+=　1
                j　+=　1
        elif j>0:
            j = N[j-1]
        else:
            i+=1
    return -1
def next(self, needle):
    m = len(needle)
    N = [0]*m
    i = 1
    j = 0
    while i<m:
        if needle[i]==needle[j]:
            N[i] = j+1
            i+=1
            j+=1
        elif j>0:
            j = N[j-1]
        else:
            N[i] = 0
            i+=1
    return N