class Solution {
  public static matchTable(str: string) {
    const strLen = str.length;
    const table: number[] = [];
    for (let pos = 0; pos < strLen; pos++) {
      let prefix: string[] = [];
      let suffix: string[] = [];
      for (let cursor = 0; cursor <= pos; cursor++) {
        prefix.push(str.slice(0, cursor));
        suffix.push(str.slice(cursor + 1, pos + 1));
      }
      prefix = prefix.filter((s) => s);
      suffix = suffix.filter((s) => s);
      const match: string[] = [""];
      prefix.forEach((pf) => {
        suffix.forEach((sf) => {
          if (pf === sf) {
            match.push(pf);
          }
        });
      });
      table.push(Math.max(...match.map((s) => s.length)));
    }
    return table;
  }

  public static matchString(target: string, search: string): number {
    const matchTable = this.matchTable(search);
    const targetLen = target.length;
    const searchLen = search.length;
    if (targetLen < searchLen) return -1;
    let pos = 0;
    while (pos <= targetLen - searchLen) {
      for (let cursor = 0; cursor < searchLen; cursor++) {
        if (target[pos + cursor] === search[cursor]) {
          if (cursor === searchLen - 1) {
            return pos;
          } else {
            continue; // for
          }
        } else {
          pos += cursor + 1 - matchTable[cursor];
          break; // for
        }
      }
    }
    return -1;
  }

  public static replace(A = "hello world", B = "hello", C = "Mars") {
    const lenA = A.length;
    const lenB = B.length;
    let res = A;
    const pos = this.matchString(res, B);
    if (pos >= 0) {
      res = res.slice(0, pos) + C + res.slice(pos + lenB, lenA);
      return res;
    } else {
      this.replace(res, B, C);
    }
    return res;
  }
}

console.log(Solution.replace("hello world", "world", "mars"));