Algorithm Analysis

for(let i = 0; i < n; i++) {
	console.log(i)
}

// Counting sort, a is the array, n is the array size. Assume the array stores non-negative integers.
public void countingSort(int[] a, int n) {
  if (n <= 1) return;
  // 1. Find the data range in the array
  int max = a[0];
  for (int i = 1; i < n; ++i) {
    if (max < a[i]) {
      max = a[i];
    }
  }
  // 2. Count
  int[] c = new int[max + 1]; // Apply for a counting array c, with index size [0, max]
  for (int i = 0; i <= max; ++i) {
    c[i] = 0;
  }
  // Calculate the count of each element and put it in c
  for (int i = 0; i < n; ++i) {
    c[a[i]]++;
  }
  // 3. Sum sequentially
  for (int i = 1; i <= max; ++i) {
    c[i] = c[i-1] + c[i];
  }
  // Temporary array r to store the sorted result
  int[] r = new int[n];
  // 4. The key step for calculating the sort, a bit hard to understand: remember to traverse the original array from back to front (to ensure it's a stable algorithm)
  for (int i = n - 1; i >= 0; --i) {
    int index = c[a[i]]-1;
    r[index] = a[i];
    c[a[i]]--;
  }
  // Copy the result to array a
  for (int i = 0; i < n; ++i) {
    a[i] = r[i];
  }
}

double number = 15; // The number whose square root is to be found
double xini = 10; // Initial point
while(xini*xini - number > 1e-6) { 
  xini = (number + xini*xini)/2/xini; 
}

int binarySearchInternal(int arr[], int low, int high, int value) {
   if(low > high) return -1; // Note 1
   int mid = low + ((high - low) >> 1); // Note 2: When optimizing mid = lo + (hi - lo) / 2 to a bit shift, be aware of operator precedence. Never write it as: mid = lo + (hi - lo) >> 1
   if(arr[mid] == value) {
       return mid;
   }
   else if(arr[mid] < value) {
	  // Note 3
       return binarySearchInternal(arr, mid + 1, high, value); 
   }
   else {
       return binarySearchInternal(arr, low, mid - 1, value);
   }
}
int binarySearch2(int arr[], int n, int value) {
   return binarySearchInternal(arr,0,n-1,value);
}

int binarySearch(int arr[], int n, int value) {
   int low = 0;
   int high = n - 1;
   // Note 1: it's <=
   while(low <= high) { 
       // Note 2: otherwise it might overflow
       int mid = low + ((high-low) >> 1); 
       if(arr[mid] == value) {
           return mid;
       }
       else if(arr[mid] < value) {
           low = mid + 1; // Note 3: need +1/-1, otherwise it might be an infinite loop
       }
       else {
           high = mid - 1;
       }
   }
   return -1;
}

int binary(int arr[], int n, int value) {
   int low = 0;
   int high = n - 1;
   while(low <= high) {
       int mid = low + ((high - low) >> 1);
       if(arr[mid] > value) {
           high = mid - 1;
       }
       else if(arr[mid] < value) {
           low = mid + 1;
       }
       else {
       // arr[mid] is the first element, or the previous one is not equal to value, then the element is found
       // otherwise, it must be on the left side
           if(mid == 0 || (arr[mid -1 ] != value)) return mid;
           else high = mid - 1;
       }
   }
   return -1;
}

int binary(int arr[], int n, int value) {
   int low = 0;
   int high = n - 1;
   while(low <= high) {
       int mid = low + ((high - low) >> 1);
       if(arr[mid] > value) {
           high = mid - 1;
       }
       else if(arr[mid] < value) {
           low = mid + 1;
       }
       else {
          // arr[mid] is the last element or the next one is not equal to value, then the element is found
          // otherwise, it must be on the right side
           if(mid == n - 1 || (arr[mid + 1 ] != value)) return mid;
           else high = mid + 1; // This should be low = mid + 1
       }
   }
   return -1;
}

int binary(int arr[], int n, int value) {
   int low = 0;
   int high = n - 1;
   while(low <= high) {
       int mid = low + ((high - low) >> 1);
       if(arr[mid] >= value) {
           // mid is the first element or the previous element is less than the value to be found
           if((mid == 0) || (arr[mid - 1] < value)) return mid;
           else high = mid - 1;
       }
       else {
           low = mid + 1;
       }
   }
   return -1;
}

int binary(int arr[], int n, int value) {
   int low = 0;
   int high = n - 1;
   while(low <= high) {
       int mid = low + ((high - low) >> 1);
       if(arr[mid] > value) {
           high = mid - 1;
       }
       else {
           // mid is the last element or the next element is greater than the value to be found
           if((mid == n - 1) || (arr[mid + 1] > value)) return mid;
           else low = mid + 1;
       }
   }
   return -1;
}

// Suppose there are n intervals. Select a subset of these intervals such that no two intervals in the subset overlap. What is the maximum number of intervals you can select?
function greedyMaxIntervals(intervals) {
  intervals = intervals.sort((a, b) => a[1] - b[1]); // Sort by end time
  let result = []; // Record the number of selected intervals
  let endTime = 0; // Record the latest end time of the currently selected intervals
  for (const [start, end] of intervals) {
    if (start >= endTime) {
      // If the start time of this interval is later than or equal to the latest end time of the currently selected intervals, it means this interval can be selected
      result.push([start, end]);
      endTime = end;
    }
  }
  return result;
}
export function TestFunction() {
  const intervals = [
    [1, 4],
    [3, 5],
    [0, 6],
    [5, 7],
    [3, 8],
    [5, 9]
  ];
  const res = greedyMaxIntervals(intervals);
  console.log(res);
  return true;
}

const mergeSort = (data, p, r) => {
    // If only one element is left, end the loop
    if(p >= r) return;
    // Temporarily divide in the middle
    let q = Math.floor((p + r) / 2);
    // Decompose
    mergeSort(data, p, q)
    mergeSort(data, q + 1, r)
    // Merge
    merge(data, p, q, r)
}
const merge = (data, p, q, r) => {
    const temp = new Array(r-p+1);
    let i = p;
    let j = q+1;
    let k = 0;
    while(i<=q &&  j <= r) {
        if(data[i] <= data[j]) {
            temp[k++] = data[i++]
        }
        else {
            temp[k++] =data[j++]
        }
    }
    // Check which array has remaining data
    let start = i;
    let end = r;
    if(j>r) {
        end = q
    }
    else {
        start = j
    }
    while(start <= end) {
        temp[k++] = data[start++]
    }
    // Copy temp back
    for(let i=0;i<r-p+1; i++) {
        data[p+i] = temp[i]
    }
    return data;
}
export const ms_test_function = () => {
    const data = [11,8,3,9,7,1,2,3]
    mergeSort(data, 0, data.length - 1)
    return true;
}

const fs = require('fs');
const path = require('path')
// Step 1: Divide the file into smaller partitions based on order amounts
function partitionFile(inputFilePath, outputDirPath, callback) {
    const partitions = {};
    // Read the input file sequentially
    const readStream = fs.createReadStream(inputFilePath, { encoding: 'utf8' });
    readStream.on('data', (chunk) => {
        const orders = chunk.split('\n');
        orders.forEach((order) => {
            // Extract the order amount from the order entry
            const amount = parseFloat(order.split(',')[1]);
            // Determine the partition for the order based on its amount
            const partition = Math.floor(amount / 100);
            // Create a writable stream for the partition file if it doesn't exist
            if (!partitions.hasOwnProperty(partition)) {
                const partitionFilePath = `${outputDirPath}/partition_${partition}.txt`;
                partitions[partition] = fs.createWriteStream(partitionFilePath, { flags: 'a' });
            }
            // Write the order to the appropriate partition file
            partitions[partition].write(`${order}\n`);
        });
    });
    readStream.on('end', () => {
        // Close all partition files
        for (const partition in partitions) {
            partitions[partition].end();
        }
        callback();
    });
}
// Step 2: Sort each partition individually
function sortPartitions(inputDirPath, outputDirPath, callback) {
    fs.readdir(inputDirPath, (err, files) => {
        if (err) {
            throw err;
        }
        files.forEach((file) => {
            const filePath = `${inputDirPath}/${file}`;
            const sortedFilePath = `${outputDirPath}/sorted_${file}`;
            // Read the orders from the partition file
            const orders = fs.readFileSync(filePath, { encoding: 'utf8' }).split('\n');
            // Sort the orders using an efficient algorithm (e.g., merge sort)
            const sortedOrders = orders.sort((a, b) => {
                const amountA = parseFloat(a.split(',')[1]);
                const amountB = parseFloat(b.split(',')[1]);
                return amountA - amountB;
            });
            // Write the sorted orders to the sorted partition file
            fs.writeFileSync(sortedFilePath, sortedOrders.join('\n'), { encoding: 'utf8' });
        });
        callback();
    });
}
// Step 3: Merge the sorted partitions
function mergePartitions(inputDirPath, outputFilePath) {
    // Step 1: Perform merge sort on an array of numbers
    function mergeSort(arr) {
        if (arr.length <= 1) {
            return arr;
        }
        const mid = Math.floor(arr.length / 2);
        const left = arr.slice(0, mid);
        const right = arr.slice(mid);
        return merge(mergeSort(left), mergeSort(right));
    }
    // Step 2: Merge two sorted arrays
    function merge(left, right) {
        let merged = [];
        let i = 0;
        let j = 0;
        while (i < left.length && j < right.length) {
            // Read the number after the file title
            if (parseFloat(left[i].split(',')[1]) <= parseFloat(right[j].split(',')[1])) {
                merged.push(left[i]);
                i++;
            } else {
                merged.push(right[j]);
                j++;
            }
        }
        while (i < left.length) {
            merged.push(left[i]);
            i++;
        }
        while (j < right.length) {
            merged.push(right[j]);
            j++;
        }
        return merged;
    }
    const filePointers = [];
    let mergedOutput = '';
    fs.readdir(inputDirPath, (err, files) => {
        if (err) {
            throw err;
        }
        // Open all sorted partition files and initialize file pointers
        files.forEach((file) => {
            const filePath = path.join(inputDirPath, file);
            const fileData = fs.readFileSync(filePath, 'utf8').trim();
            const partitionData = fileData.split('\n');
            filePointers.push(partitionData);
        });
        // Merge the sorted partitions
        const sortedOutput = mergeSort(filePointers.flat());
        // Format the sorted output
        mergedOutput = sortedOutput.join('\n') + '\n';
        // Write the merged output to the final sorted file
        fs.writeFileSync(outputFilePath, mergedOutput, { encoding: 'utf8' });
        // Delete the temporary partition files
        // files.forEach((file) => {
        //     const filePath = path.join(inputDirPath, file);
        //     fs.unlinkSync(filePath);
        // });
    });
}
// Entry point
function sortLargeOrderFile(inputFilePath, outputFilePath) {
    const inputDirPath = './temp/input';
    const outputDirPath = './temp/output';
    // Create temporary directories if they don't exist
    if (!fs.existsSync('./temp')) {
        fs.mkdirSync('./temp');
    }
    if (!fs.existsSync(inputDirPath)) {
        fs.mkdirSync(inputDirPath);
    }
    if (!fs.existsSync(outputDirPath)) {
        fs.mkdirSync(outputDirPath);
    }
    partitionFile(inputFilePath, inputDirPath, () => {
        sortPartitions(inputDirPath, outputDirPath, () => {
            mergePartitions(outputDirPath, outputFilePath);
        });
    });
}
// Usage
const inputFilePath = './input_file.txt';
const outputFilePath = './sorted_file.txt';
sortLargeOrderFile(inputFilePath, outputFilePath);

let minDist: number = Number.MAX_VALUE;
/**
 * Backtracking method to calculate the minimum distance.
 * @param i x-coordinate position
 * @param j y-coordinate position
 * @param dist current distance
 * @param w table array
 * @param n array length
 */
const minDistBT = (
  i: number,
  j: number,
  dist: number,
  w: Array<Array<number>>,
  n: number
) => {
  dist += w[i][j];
  // Reached the destination
  if (i === n - 1 && j === n - 1) {
    if (dist < minDist) {
      minDist = dist;
      return;
    }
  }
  // Move one step to the right
  if (i < n - 1) {
    minDistBT(i + 1, j, dist, w, n);
  }
  // Move one step down
  if (j < n - 1) {
    minDistBT(i, j + 1, dist, w, n);
  }
};
export function TestFunction() {
  let dist: number = 0;
  let w: Array<Array<number>> = [
    [1, 2, 5],
    [3, 2, 1],
    [9, 2, 11]
  ];
  minDistBT(0, 0, dist, w, 3);
  console.log(minDist);
  return true;
}

[
   [1, 2, 5],
   [3, 2, 1],
   [9, 2, 11]
 ];

let mem: Array<Array<number>> = new Array(3)
  .fill(0)
  .map(() => new Array(3).fill(0));
function minDistDP(
  maxtrix: Array<Array<number>>,
  i: number,
  j: number
): number {
  if (i === 0 && j === 0) {
    return maxtrix[0][0];
  }
  if (mem[i][j] > 0) return mem[i][j];
  let minLeft = Number.MAX_VALUE;
  if (j - 1 >= 0) {
    minLeft = minDistDP(maxtrix, i, j - 1);
  }
  let minTop = Number.MAX_VALUE;
  if (i - 1 >= 0) {
    minTop = minDistDP(maxtrix, i - 1, j);
  }
  let currentMinDist = maxtrix[i][j] + Math.min(minLeft, minTop);
  mem[i][j] = currentMinDist;
  return currentMinDist;
}

/**
 * Double 11 discount problem
 * @param items  Product prices
 * @param n Number of products
 * @param w Target amount for discount
 */
function double11advance(items, n, w) {
    let states = new Array(n); // Initialize state table
    for (let i = 0; i < n; i++) {
        states[i] = new Array(3 * w + 1).fill(false);
    }
    states[0][0] = true; // First decision
    if (items[0] <= 3 * w) {
        states[0][items[0]] = true;
    }
    for (let i = 1; i < n; i++) {
        for (let j = 0; j <= 3 * w; j++) { // Do not select
            if (states[i - 1][j] === true) {
                states[i][j] = states[i - 1][j]; // State remains the same as the previous one
            }
        }
        for (let j = 0; j <= 3 * w - items[i]; j++) { // Select
            if (states[i - 1][j] === true) {
                states[i][j + items[i]] = true; // Mark this point as decided
            }
        }
    }
    let j;
    for (j = w; j < 3 * w + 1; j++) { // Find the decision price closest to 200
        if (states[n - 1][j] === true) {
            break;
        }
    }
    if (j === 3 * w + 1) { // Cannot find such a combination
        return;
    }
    for (let i = n - 1; i >= 1; i--) { // Start from the first product
        // Check from n products, if the previous marked point [i-1, j-items[i]] is marked as 1, it means this product was selected
        if (j - items[i] > 0 && states[i - 1][j - items[i]] === true) {
            console.log(items[i] + " ");// Print selected product
            j = j - items[i];
        }
    }
    if (j !== 0) { // If there is still money left, it means the 0th product was also selected (because our state table is derived from the previous state to the next). If the 0th was not bought, j would be 0 here. If j is not 0, it means the 0th was bought.
        console.log(items[0]);
    }
}
export const dy_test_function = () => {
    // Select from these products to reach exactly 10 yuan for the discount
    const items = [2,2,4,6,3]
    double11advance(items, items.length, 10)
    return true
}

const SIZE = 256;
// Save the character index of the pattern string
function generateBC(bc: Array<number>, b: string) {
  for (let i = 0; i < b.length; i++) {
    const ascii = b[i].charCodeAt(0); // Convert to ASCII value of b[i]
    bc[ascii] = i;
  }
}
/**
 * Bad character matching algorithm implementation
 * @param a main string
 * @param b pattern string
 */
function bm_bc(a: string, b: string) {
  // Used to store the index corresponding to each character in the pattern string
  const bc: number[] = new Array(SIZE).fill(-1);
  generateBC(bc, b); // Generate a 256-bit ASCII array to store character indices, avoiding search by traversal
  let n = a.length; // length of the main string
  let m = b.length; // length of the pattern string
  // Represents the first character where the main string and pattern string are aligned
  let i = 0;
  while (i <= n - m) {
    // When the first character is smaller than the length difference between the main and pattern strings, it means no more backward movement is needed
    let j;
    // Pattern string matches from back to front
    for (j = m - 1; j >= 0; j--) {
      // Mismatch. Index j is the position of the bad character in the pattern string
      if (a[i + j] !== b[j]) {
        break;
      }
    }
    // Match successful. Return the first matching position of the pattern and main strings
    if (j <= 0) {
      return i;
    }
    // Move the pattern string backward: according to the bad character rule, si - xi
    // xi: a[i+j] the position of this bad character in the pattern string
    // si: j
    i = i + (j - bc[a[i + j].charCodeAt(0)]);
  }
  return -1; // No match found
}
// Through the above three diagrams, to calculate the number of bits to shift right, we need to know
// The matching index of the good suffix string {u} and another substring {u*}, which is x
// We build an array suffix[length of substring] = x
/**
 * @param b pattern string
 * @param suffix
 * @param prefix
 * @param m
 */
function generateSuffix(b: string, suffix: number[], prefix: boolean[], m) {
  for(let i = 0; i < m - 1; i++) { // traverse b
    let j = i;
    let k = 0; // length of the common suffix substring
    // Compare head and tail elements, if equal, move the head element forward, continue comparing two, three lengths
    while(j >= 0 && b[j] == b[m - 1 - k]) {
      --j;
      ++k;
      suffix[k] = j + 1;
    }
    if(j === -1) {
      prefix[k] = true; // It is the longest substring. Because we are looking for the longest substring
    }
  }
}
function moveByGS(j: number, m: number, suffix: number[], prefix: boolean[]) {
  let k = m - 1 - j; // length of the good suffix
  // 1. Perfect match
  if(suffix[k] !== -1) { // Indicates that the longest common suffix substring exists, find bc first, then c
    return j - suffix[k] + 1;
  }
  // 2. Partial match
  for(let r = j + 2; r <= m -1; ++r) {
    if(prefix[m-1-r+1]) { // This is our longest common substring
      return r
    }
  }
  // 3. Mismatch
  return m;
}
/**
 * @param a main string
 * @param b pattern string
 */
function bm(a: string, b: string) {
  // Used to store the index corresponding to each character in the pattern string
  const bc: number[] = new Array(SIZE).fill(-1);
  generateBC(bc, b); // Generate a 256-bit ASCII array to store character indices, avoiding search by traversal
  let suffix = new Array(b.length).fill(-1);
  let prefix = new Array(b.length).fill(false);
  let n = a.length;
  let m = b.length;
  generateSuffix(b, suffix, prefix, m);
  // Represents the first character where the main string and pattern string are aligned
  let i = 0;
  while (i <= n - m) {
    // When the first character is smaller than the length difference between the main and pattern strings, it means no more backward movement is needed
    let j;
    // Pattern string matches from back to front
    for (j = m - 1; j >= 0; j--) {
      // Mismatch. Index j is the position of the bad character in the pattern string
      if (a[i + j] !== b[j]) {
        break;
      }
    }
    // Match successful. Return the first matching position of the pattern and main strings
    if (j <= 0) {
      return i;
    }
    // Move the pattern string backward: according to the bad character rule, si - xi
    // si: a[i+j] the position of this bad character in the pattern string
    // xi: j
    let x = j - bc[a[i + j].charCodeAt(0)]; // length of bad character movement
    let y = 0;
    if(j < m - 1) { // has good suffix
      y = moveByGS(j, m, suffix, prefix); // length of good character movement
    }
    i = i + Math.max(x, y);
  }
  return -1; // No match found
}
export function BMTestFunction() {
  const a = "abcacabdc";
  const b = "abd";
  const result = bm(a, b);
  console.log(result);
  return result;
}
export function BM_BC_TestFunction() {
  const a = "abcacabdc";
  const b = "abd";
  const result = bm_bc(a, b);
  console.log(result);
  return result;
}

function genNexts(b) {
    let m = b.length;
    let next = new Array(m);
    next[0] = -1;
    let k = -1; // prefix substring of the good prefix
    for(let i =1; i< m;i++) {
        // case 2: loop to find
        while(k !== -1 && b[k+1] != b[i]) {
            k = next[k]
        }
        // case 1
        if(b[k+1] === b[i]) {
            ++k;
        }
        // record it
        next[i] = k;
    }
    return next;    
}
function kmp(a, b) {
    let n = a.length; 
    let m = b.length; // pattern string length
    let next = genNexts(b, m); // only related to the pattern string
    let j = 0; // pattern string index
    for(let i=0; i<n; i++) {
        while(j > 0 && a[i] !== b[j]) { // found a bad character
            j = next[j-1] + 1; // j is updated to k. 
        }
        if(a[i] === b[j]) { // equal case
            ++j; // move pattern string index
        }  
        if(j == m) { // found a matching character, return the position of i
            return  i - m + 1;
        }
    }
    return -1; // no match found
}
export function kmp_TestFunction() {
  const a = "abcacabdc";
  const b = "abd";
  const result = kmp(a, b);
  console.log(result);
  return result;
}

// Calculate hash values for the n-m+1 substrings in the main string, then compare the hash value of the pattern string with each of them.
const alphabetSize = 26;
const rk = (text, pattern) => {
  const m = pattern.length;
  const n = text.length;
  const h = [];
  const calculateHash = (s, i) => {
    if (i === 0) {
      let total = 0;
      for (let i = 0; i < m; i++) {
        total +=
          (s[i].charCodeAt(0) - "a".charCodeAt(0)) * Math.pow(alphabetSize, m - i + 1);
      }
      h[0] = total;
    } else {
      // h[i] = (h[i-1] - (s[i-1] - 'a')*26^m-1) * 26 + (s[i+m-1]-'a') * 26^0
      h[i] =
        (h[i - 1] -
          (s[i - 1].charCodeAt(0) - "a".charCodeAt(0)) * Math.pow(alphabetSize, m - 1)) *
          alphabetSize +
        s[i + m - 1].charCodeAt(0) -
        "a".charCodeAt(0);
    }
    return h[i];
  };
  const p_hash = calculateHash(pattern, 0);
  for (let i = 0; i <= n - m; i++) {
    const t_hash = calculateHash(text, i);
    if (p_hash === t_hash) {
      return i;
    }
  }
  return -1;
};
export function rk_TestFunction() {
  const a = "abca";
  const b = "bca";
  const result = rk(a, b);
  console.log(result);
  return result;
}

function createAcNode(data) {
    return {
        data,
        children: new Array(26).fill(null),
        isEndingChar: false,
        length: -1,
        fail: null,
    };
}
// Create on the dictionary
const createTrie = () => {
    const root = createAcNode("/");
    const insert = (words: string) => {
        let p = root;
        Array.from(words).forEach((c: string) => {
            let index: number = c.charCodeAt(0) - "a".charCodeAt(0);
            // create new node
            if (p.children[index] === null) {
                p.children[index] = createAcNode(c);
            }
            // point to new node
            p = p.children[index];
        });
        // mark as end of word node
        p.isEndingChar = true;
        p.length = words.length;
    };
    return {
        insert,
        root
    };
};
//-----------------------
function buildFailurePointer(root) {
  const queue = [];
  root.fail = null; // mark root node
  queue.push(root);
  while (queue.length > 0) {
    const p = queue.shift(); // p is the current pointer of the trie
    for (let i = 0; i < 26; i++) { // when traversing child nodes
      const pc = p.children[i]; // pc is a child node of p
      if (pc === null) { // skip empty child nodes
        continue;
      }
      if (p === root) { // all child nodes of the root node have their fail pointers pointing to the root node
        pc.fail = root;
      }
      else { // not the root node, i.e., p
        let q = p.fail; // the position of the current node's failure pointer
        while (q !== null) {
          const qc = q.children[pc.data.charCodeAt(0) - "a".charCodeAt(0)];
          if (qc !== null) { // if qc exists, point pc's failure pointer to qc and stop searching
            pc.fail = qc;
            break;
          }
          // if such a qc does not exist, find the previous matchable suffix substring
          q = q.fail;
        }
        // reached the root node, point pc's failure pointer to root
        if (q === null) {
          pc.fail = root;
        }
      }
      queue.push(pc);
    }
  }
}
function match(root, text) {
  const n = text.length;
  let p = root; // start from the root node
  for (let i = 0; i < n; i++) { // scan the main string once
    const idx = text[i].charCodeAt(0) - "a".charCodeAt(0); // get the array index of the current character
    // p.children[idx] means the child node of pointer p finds the corresponding character of the main string
    while (p.children[idx] === null && p !== root) { // in this case, it is not equal to the main string, so search through the failure pointer
      p = p.fail;
    }
    p = p.children[idx]; // level order traversal, point to child node
    if (p === null) { // if there is no match, e.g., in this case, restart matching from root
      p = root;
    }
    // check if a series of paths ending with a failure pointer is a pattern string, if so, this pattern string is a sensitive word
    let tmp = p; // child node is not null
    while (tmp !== root) { // until the pointer points to the root node
      if (tmp.isEndingChar) { // determine if it is a pattern string, if so, it means this pattern string is a sensitive word, then print the result
        const pos = i - tmp.length + 1;
        console.log("start index,",pos, "length", tmp.length);
      }
      // otherwise, check along the failure pointer
      tmp = tmp.fail;
    }
  }
}
export function ac_TestFunction() {
    const trie = createTrie();
    const { insert, root } = trie;
    insert("c");
    insert("bc");
    insert("bcd");
    insert("abcd");
    buildFailurePointer(root);
    match(root, "abcd")
    return null
}

const createNode = (char, frequency) => {
    return {
        char,
        frequency,
        left: null,
        right: null
    }
}
const buildHuffmanTree = (data) => {
    // Array of nodes sorted in ascending order of frequency
    const nodes = Object.entries(data).map(([char, value]) => {
        return createNode(char, data[char])
    })
    // Build Huffman tree
    while(nodes.length > 1) {
        // sort in ascending order
        nodes.sort((a,b) => a.frequency - b.frequency)
        const left = nodes.shift()
        const right = nodes.shift()
        const parent = createNode(null, left.frequency + right.frequency)
        parent.left = left;
        parent.right = right;
        nodes.push(parent)
    }
    // root node
    return nodes[0]
}
const buildHuffmanTable = root => {
    const huffmanTable = {}
    // Traverse edges: preorder traversal
    const  traverse = (node, code) => {
        if(node.char) { // leaf node
            console.log('node.char', node.char)
            huffmanTable[node.char] = code
        }
        else { // non-leaf node
            traverse(node.left, code + '0')
            traverse(node.right, code + '1')
        }
    }
    traverse(root, '');
    console.log('hu', huffmanTable)
    return huffmanTable
}
// Get Huffman encoding: path of the tree
function huffmanEncoding(data) {
    const root = buildHuffmanTree(data)
    const huffmanTable = buildHuffmanTable(root)
    let encodedData  = ''
    for(let symbol in data) {
        encodedData += huffmanTable[symbol] + " "
    }
    return encodedData.trim()
}
export function hf_TestFunction() {
    const data = {
        'a': 450,
        'b': 350,
        'c': 90,
        'd': 60,
        'e': 30,
        'f': 20,
    };
    const encodedData = huffmanEncoding(data);
    console.log(encodedData);
    return null;
}

function lwstDP(a, n, b, m) {
    const minDist = new Array(n + 1);
    for (let i = 0; i < n + 1; i++) {
        minDist[i] = new Array(m + 1);
        minDist[i][0] = i;
    }
    for (let j = 0; j < m + 1; j++) {
        minDist[0][j] = j;
    }
    for (let i = 1; i < n + 1; i++) {
        for (let j = 1; j < m + 1; j++) {
            if (a[i - 1] === b[j - 1]) {
                minDist[i][j] = minOfThree(
                    minDist[i - 1][j] + 1,
                    minDist[i][j - 1] + 1,
                    minDist[i - 1][j - 1]
                );
            } else {
                minDist[i][j] = minOfThree(
                    minDist[i - 1][j] + 1,
                    minDist[i][j - 1] + 1,
                    minDist[i - 1][j - 1] + 1
                );
            }
        }
    }
    return minDist[n][m];
}
function minOfThree(n1, n2, n3) {
    return Math.min(n1, Math.min(n2, n3));
}