28. 找出字符串中第一个匹配项的下标

题目链接

const getNext = (src: string) => {
    let preMatchLen = 0; // 当前匹配到的前缀长度
    let i = 0;
    const next:number[] =[]; // 某个位置的后缀能够匹配的最大前缀长度；
    next[i] = preMatchLen; 
    for (i = 1;i<src.length;i++) {
        while(src[i] != src[preMatchLen]) {
            if(preMatchLen <= 0)break;
            preMatchLen = next[preMatchLen - 1];
        }
        if (src[i] === src[preMatchLen]) {
            preMatchLen += 1;
        } 
        next[i] = preMatchLen;
    }
    return next;
}

function strStr(haystack: string, needle: string): number {
    let matchLen = 0;
    const next = getNext(needle);
    for (let i = 0;i<haystack.length;i++) {
        while(matchLen>0 && haystack[i] !== needle[matchLen]) {
            matchLen = next[matchLen - 1];
        }
        if (haystack[i] === needle[matchLen]) {
            matchLen += 1;
        }
        if (matchLen === needle.length) {
            return i - matchLen + 1;
        }
    }
    return -1;
};


(()=>{
    console.log('getNext', getNext('aabaac'));
    console.log('strStr' , strStr("dfasdsasadbutsad", "sad"));
})()