execute.html

<script>
  // function match(string) {
  //   let foundA = false
  //   let foundB = false
  //   let foundC = false
  //   let foundD = false
  //   let foundE = false
  //   for (let char of string) {
  //     if (char == 'a')
  //       foundA = true
  //     else if (foundA && char == 'b')
  //       foundB = true
  //     else if (foundB && char == 'c')
  //       foundC = true
  //     else if (foundC && char == 'd')
  //       foundD = true
  //     else if (foundD && char == 'e')
  //       foundE = true
  //     else if (foundD && char == 'f')
  //       return true
  //     else {
  //       let foundA = false
  //       let foundB = false
  //       let foundC = false
  //       let foundD = false
  //       let foundE = false
  //     }
  //   }
  //   return false
  // }
  // match("I aabcdefghm grood.")

  // function match(string) {
  //   let state = start
  //   for (let char of string) {
  //     state = state(char)
  //   }
  //   return state === end
  // }
  // function start(char) {
  //   if (char === 'a')
  //     return findA
  //   else
  //     return start
  // }
  // function end(char) {
  //   return end
  // }
  // function findA(char) {
  //   if (char === 'b')
  //     return findB
  //   else
  //     return start(char)
  // }
  // function findB(char) {
  //   if (char === 'c')
  //     return findC
  //   else
  //     return start(char)
  // }
  // function findC(char) {
  //   if (char === 'd')
  //     return findD
  //   else
  //     return start(char)
  // }
  // function findD(char) {
  //   if (char === 'e')
  //     return findE
  //   else
  //     return start(char)
  // }
  // function findE(char) {
  //   if (char === 'f')
  //     return end
  //   else
  //     return start
  // }
  // console.log(match("I aabcdefghm grood."))
  // console.log(match("I aacdefghm grood."))

  // function match(string) {
  //   let state = start
  //   for (let char of string) {
  //     state = state(char)
  //   }
  //   return state === end
  // }
  // function start(char) {
  //   if (char === 'a')
  //     return findA
  //   else
  //     return start
  // }
  // function end(char) {
  //   return end
  // }
  // function findA(char) {
  //   if (char === 'b')
  //     return findB
  //   else
  //     return start(char)
  // }
  // function findB(char) {
  //   if (char === 'c')
  //     return findC
  //   else
  //     return start(char)
  // }
  // function findC(char) {
  //   if (char === 'a')
  //     return findA2
  //   else
  //     return start(char)
  // }
  // function findA2(char) {
  //   if (char === 'b')
  //     return findB2
  //   else
  //     return start(char)
  // }
  // function findB2(char) {
  //   if (char === 'x')
  //     return end
  //   else
  //     return findB(char)
  // }
  // console.log(match("I aabcabcabx grood."))
  // console.log(match("I aabcabcabcabx grood."))
  // console.log(match("I aabcabcabxabx grood."))
  // console.log(match("I aabcabcababx grood."))


  // function match(string) {
  //   let state = start
  //   for (let char of string) {
  //     state = state(char)
  //   }
  //   return state === end
  // }
  // function start(char) {
  //   if (char === 'a')
  //     return findA1
  //   else
  //     return start
  // }
  // function end(char) {
  //   return end
  // }
  // function findA1(char) {
  //   if (char === 'b')
  //     return findB1
  //   else
  //     return start(char)
  // }
  // function findB1(char) {
  //   if (char === 'a')
  //     return findA2
  //   else
  //     return start(char)
  // }
  // function findA2(char) {
  //   if (char === 'b')
  //     return findB2
  //   else
  //     return start(char)
  // }
  // function findB2(char) {
  //   if (char === 'a')
  //     return findA3
  //   else
  //     return start(char)
  // }
  // function findA3(char) {
  //   if (char === 'b')
  //     return findB3
  //   else
  //     return start(char)
  // }
  // function findB3(char) {
  //   if (char === 'x')
  //     return end
  //   else
  //     return findB2(char)
  // }
  // console.log(match("I aababababx grood."))
  // console.log(match("I aabababababx grood."))
  // console.log(match("I aababaeababx grood."))
  // console.log(match("I aabababaabx grood."))


  // function prefixTable(pattern, prefix, n) {
  //   prefix[0] = 0; // prefix 初始
  //   let len = 0; // 最长公共前后缀长度
  //   let i = 1;
  //   while(i < n) {
  //     if (pattern[i] === pattern[len]) {
  //       len ++;
  //       prefix[i] = len;
  //       i ++;
  //     } else {
  //       if (len > 0) {
  //         len = prefix[len - 1]
  //       }
  //       else {
  //         prefix[i] = len
  //         i ++
  //       }
  //     }
  //     console.log(prefix)
  //   }
  // }

  // function movePrefixTable(prefix, n) {
  //   for (let i = n - 1; i > 0; i --) {
  //     prefix[i] = prefix[i - 1]
  //   }
  //   prefix[0] = -1
  // }

  // function kmpSearch(text, pattern) {
  //   const patternArray = pattern.split("")
  //   let patternLen = patternArray.length
  //   const textArray = text.split("")
  //   let textLen = textArray.length

  //   let prefixArray = new Array(patternLen)
  //   prefixTable(patternArray, prefixArray, patternLen)
  //   movePrefixTable(prefixArray, patternLen)

  //   // console.log('prefixTemp', prefixTemp)
  //   console.log('prefixArray', prefixArray)

  //   // textArray len m
  //   // pattern len n

  //   let i = 0, j = 0;
  //   while(i < textLen) {
  //     if (j === patternLen - 1 && textArray[i] === patternArray[j]) {
  //       console.log("Found pattern at ", i - j)
  //       j = prefixArray[j]
  //     }
  //     if (textArray[i] === patternArray[j]) {
  //       i ++;
  //       j ++;
  //     } else {
  //       j = prefixArray[j]
  //       if (j === -1) {
  //         i ++;
  //         j ++;
  //       }
  //     }
  //   }
  // }

  // kmpSearch("ABABABABCABAAB", "ABABCABAA")

  function movePrefixTable(prefix, n) {
    for (let i = n - 1; i > 0; i --) {
      prefix[i] = prefix[i - 1]
    }
    prefix[0] = -1
  }

  function match(text, pattern) {
    const patternArray = pattern.split("")
    let patternLen = patternArray.length
    const textArray = text.split("")
    let textLen = textArray.length
    let prefixArray = new Array(patternLen)

    let patternState = patteranStart
    prefixArray[0] = 0
    let len = 0
    let res = {len: 0, needAdd: true}
    for (let i = 1; i < patternLen; res.needAdd && i ++) {
      res = patternState(i, pattern, len, prefixArray)
      len = res.len
    }

    movePrefixTable(prefixArray, patternLen)

    let i = 0, j = 0;
    while(i < textLen) {
      if (j === patternLen - 1 && textArray[i] === patternArray[j]) {
        console.log("Found pattern at ", i - j)
        j = prefixArray[j]
        return true
      }
      if (textArray[i] === patternArray[j]) {
        i ++;
        j ++;
      } else {
        j = prefixArray[j]
        if (j === -1) {
          i ++;
          j ++;
        }
      }
    }
    return false
  }

  function patteranStart(i, pattern, len, prefix) {
      if (pattern[i] === pattern[len]) {
        len ++;
        prefix[i] = len;
        return {len, needAdd: true};
      } else {
        if (len > 0) {
          len = prefix[len - 1]
          return {len, needAdd: false}
        }
        else {
          prefix[i] = len
          return {len, needAdd: true}
        }
      }
  }

  match("ABABABABCABAAB", "ABABCABAA")
</script>