class SkipListNode<T> {
  value: T;
  forward: SkipListNode<T>[];

  constructor(value: T, level: number) {
    this.value = value;
    this.forward = new Array(level + 1).fill(null);
  }
}

class SkipList<T> {
  private head: SkipListNode<T>;
  private maxLevel: number;
  private level: number;
  private p: number; // 概率因子

  constructor(maxLevel: number = 16, p: number = 0.5) {
    this.maxLevel = maxLevel;
    this.level = 0;
    this.p = p;
    this.head = new SkipListNode<T>(null as any, maxLevel);
  }

  private randomLevel(): number {
    let level = 0;
    while (Math.random() < this.p && level < this.maxLevel) {
      level++;
    }
    return level;
  }

  insert(value: T): void {
    const update: SkipListNode<T>[] = new Array(this.maxLevel + 1).fill(this.head);
    let current = this.head;

    // 找到插入位置
    for (let i = this.level; i >= 0; i--) {
      while (current.forward[i] && current.forward[i].value < value) {
        current = current.forward[i];
      }
      update[i] = current;
    }

    const newLevel = this.randomLevel();
    if (newLevel > this.level) {
      for (let i = this.level + 1; i <= newLevel; i++) {
        update[i] = this.head;
      }
      this.level = newLevel;
    }

    const newNode = new SkipListNode<T>(value, newLevel);

    // 更新指针
    for (let i = 0; i <= newLevel; i++) {
      newNode.forward[i] = update[i].forward[i];
      update[i].forward[i] = newNode;
    }
  }

  search(value: T): boolean {
    let current = this.head;

    for (let i = this.level; i >= 0; i--) {
      while (current.forward[i] && current.forward[i].value < value) {
        current = current.forward[i];
      }
    }

    current = current.forward[0];
    return current !== null && current.value === value;
  }

  delete(value: T): boolean {
    const update: SkipListNode<T>[] = new Array(this.maxLevel + 1).fill(this.head);
    let current = this.head;

    // 找到删除位置
    for (let i = this.level; i >= 0; i--) {
      while (current.forward[i] && current.forward[i].value < value) {
        current = current.forward[i];
      }
      update[i] = current;
    }

    current = current.forward[0];

    if (!current || current.value !== value) {
      return false;
    }

    // 更新指针
    for (let i = 0; i <= this.level; i++) {
      if (update[i].forward[i] !== current) {
        break;
      }
      update[i].forward[i] = current.forward[i];
    }

    // 降低层级
    while (this.level > 0 && this.head.forward[this.level] === null) {
      this.level--;
    }

    return true;
  }

  print(): void {
    for (let i = 0; i <= this.level; i++) {
      let current = this.head.forward[i];
      const levelStr = `Level ${i}: `;
      let str = levelStr;
      while (current) {
        str += `${current.value} -> `;
        current = current.forward[i];
      }
      str += 'null';
      console.log(str);
    }
  }
}

class BTreeNode<T> {
  keys: T[];
  children: BTreeNode<T>[];
  isLeaf: boolean;
  t: number; // 最小度数

  constructor(t: number, isLeaf: boolean = true) {
    this.t = t;
    this.isLeaf = isLeaf;
    this.keys = [];
    this.children = [];
  }
}

class BTree<T> {
  private root: BTreeNode<T> | null;
  private t: number; // 最小度数

  constructor(t: number) {
    this.root = null;
    this.t = t;
  }

  search(key: T): boolean {
    return this.searchNode(this.root, key);
  }

  private searchNode(node: BTreeNode<T> | null, key: T): boolean {
    if (!node) return false;

    let i = 0;
    while (i < node.keys.length && key > node.keys[i]) {
      i++;
    }

    if (i < node.keys.length && key === node.keys[i]) {
      return true;
    }

    if (node.isLeaf) {
      return false;
    }

    return this.searchNode(node.children[i], key);
  }

  insert(key: T): void {
    if (!this.root) {
      this.root = new BTreeNode<T>(this.t, true);
      this.root.keys.push(key);
      return;
    }

    if (this.root.keys.length === 2 * this.t - 1) {
      const newRoot = new BTreeNode<T>(this.t, false);
      newRoot.children.push(this.root);
      this.splitChild(newRoot, 0);
      this.root = newRoot;
    }

    this.insertNonFull(this.root, key);
  }

  private insertNonFull(node: BTreeNode<T>, key: T): void {
    let i = node.keys.length - 1;

    if (node.isLeaf) {
      // 找到插入位置
      while (i >= 0 && key < node.keys[i]) {
        i--;
      }
      node.keys.splice(i + 1, 0, key);
    } else {
      // 找到子节点
      while (i >= 0 && key < node.keys[i]) {
        i--;
      }
      i++;

      if (node.children[i].keys.length === 2 * this.t - 1) {
        this.splitChild(node, i);
        if (key > node.keys[i]) {
          i++;
        }
      }

      this.insertNonFull(node.children[i], key);
    }
  }

  private splitChild(parent: BTreeNode<T>, i: number): void {
    const child = parent.children[i];
    const newChild = new BTreeNode<T>(this.t, child.isLeaf);

    // 提升中间键到父节点
    const midKey = child.keys[this.t - 1];
    parent.keys.splice(i, 0, midKey);
    parent.children.splice(i + 1, 0, newChild);

    // 移动右半部分到新节点
    newChild.keys = child.keys.splice(this.t);
    if (!child.isLeaf) {
      newChild.children = child.children.splice(this.t);
    }
  }

  delete(key: T): boolean {
    if (!this.root) return false;

    const result = this.deleteFromNode(this.root, key);

    // 如果根节点为空，降低树高
    if (this.root.keys.length === 0 && !this.root.isLeaf) {
      this.root = this.root.children[0];
    }

    return result;
  }

  private deleteFromNode(node: BTreeNode<T>, key: T): boolean {
    let i = 0;
    while (i < node.keys.length && key > node.keys[i]) {
      i++;
    }

    if (i < node.keys.length && key === node.keys[i]) {
      if (node.isLeaf) {
        // 从叶节点删除
        node.keys.splice(i, 1);
        return true;
      } else {
        // 从内部节点删除
        return this.deleteFromInternalNode(node, i);
      }
    } else {
      if (node.isLeaf) {
        return false;
      }

      const flag = i === node.keys.length;

      // 确保子节点至少有 t 个键
      if (node.children[i].keys.length < this.t) {
        this.fill(node, i);
      }

      if (flag && i > node.keys.length) {
        return this.deleteFromNode(node.children[i - 1], key);
      } else {
        return this.deleteFromNode(node.children[i], key);
      }
    }
  }

  private deleteFromInternalNode(node: BTreeNode<T>, i: number): boolean {
    const key = node.keys[i];

    if (node.children[i].keys.length >= this.t) {
      // 前驱替换
      const pred = this.getPredecessor(node.children[i]);
      node.keys[i] = pred;
      return this.deleteFromNode(node.children[i], pred);
    } else if (node.children[i + 1].keys.length >= this.t) {
      // 后继替换
      const succ = this.getSuccessor(node.children[i + 1]);
      node.keys[i] = succ;
      return this.deleteFromNode(node.children[i + 1], succ);
    } else {
      // 合并子节点
      this.merge(node, i);
      return this.deleteFromNode(node.children[i], key);
    }
  }

  private getPredecessor(node: BTreeNode<T>): T {
    let current = node;
    while (!current.isLeaf) {
      current = current.children[current.children.length - 1];
    }
    return current.keys[current.keys.length - 1];
  }

  private getSuccessor(node: BTreeNode<T>): T {
    let current = node;
    while (!current.isLeaf) {
      current = current.children[0];
    }
    return current.keys[0];
  }

  private fill(node: BTreeNode<T>, i: number): void {
    if (i !== 0 && node.children[i - 1].keys.length >= this.t) {
      this.borrowFromPrev(node, i);
    } else if (i !== node.keys.length && node.children[i + 1].keys.length >= this.t) {
      this.borrowFromNext(node, i);
    } else {
      if (i !== node.keys.length) {
        this.merge(node, i);
      } else {
        this.merge(node, i - 1);
      }
    }
  }

  private borrowFromPrev(node: BTreeNode<T>, i: number): void {
    const child = node.children[i];
    const sibling = node.children[i - 1];

    // 移动父节点的键到子节点开头
    child.keys.unshift(node.keys[i - 1]);

    // 移动兄弟节点的最后一个键到父节点
    node.keys[i - 1] = sibling.keys.pop()!;

    // 移动兄弟节点的子节点
    if (!child.isLeaf) {
      child.children.unshift(sibling.children.pop()!);
    }
  }

  private borrowFromNext(node: BTreeNode<T>, i: number): void {
    const child = node.children[i];
    const sibling = node.children[i + 1];

    // 移动父节点的键到子节点末尾
    child.keys.push(node.keys[i]);

    // 移动兄弟节点的第一个键到父节点
    node.keys[i] = sibling.keys.shift()!;

    // 移动兄弟节点的子节点
    if (!child.isLeaf) {
      child.children.push(sibling.children.shift()!);
    }
  }

  private merge(node: BTreeNode<T>, i: number): void {
    const child = node.children[i];
    const sibling = node.children[i + 1];

    // 移动父节点的键到子节点
    child.keys.push(node.keys.splice(i, 1)[0]);

    // 移动兄弟节点的所有键和子节点
    child.keys.push(...sibling.keys);
    if (!child.isLeaf) {
      child.children.push(...sibling.children);
    }

    // 移除兄弟节点
    node.children.splice(i + 1, 1);
  }
}

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEndOfWord: boolean = false;
  count: number = 0; // 记录经过此节点的单词数量
}

class Trie {
  private root: TrieNode = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
      node.count++;
    }
    node.isEndOfWord = true;
  }

  search(word: string): boolean {
    const node = this.getNode(word);
    return node !== null && node.isEndOfWord;
  }

  startsWith(prefix: string): boolean {
    return this.getNode(prefix) !== null;
  }

  getNode(word: string): TrieNode | null {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        return null;
      }
      node = node.children.get(char)!;
    }
    return node;
  }

  // 获取以指定前缀开头的单词数量
  countWordsStartingWith(prefix: string): number {
    const node = this.getNode(prefix);
    return node ? node.count : 0;
  }

  // 删除单词
  delete(word: string): boolean {
    let node = this.root;
    const nodes: TrieNode[] = [node];

    for (const char of word) {
      if (!node.children.has(char)) {
        return false;
      }
      node = node.children.get(char)!;
      nodes.push(node);
    }

    if (!node.isEndOfWord) {
      return false;
    }

    node.isEndOfWord = false;

    // 从后往前清理不需要的节点
    for (let i = nodes.length - 1; i >= 0; i--) {
      const currentNode = nodes[i];
      currentNode.count--;

      if (currentNode.count === 0 && !currentNode.isEndOfWord) {
        const parent = nodes[i - 1];
        if (parent) {
          const char = word[i - 1];
          parent.children.delete(char);
        }
      }
    }

    return true;
  }

  // 获取所有单词
  getAllWords(): string[] {
    const result: string[] = [];
    this.collectWords(this.root, '', result);
    return result;
  }

  private collectWords(node: TrieNode, prefix: string, result: string[]): void {
    if (node.isEndOfWord) {
      result.push(prefix);
    }

    for (const [char, childNode] of node.children) {
      this.collectWords(childNode, prefix + char, result);
    }
  }

  // 获取以指定前缀开头的单词
  getWordsWithPrefix(prefix: string): string[] {
    const node = this.getNode(prefix);
    if (!node) return [];

    const result: string[] = [];
    this.collectWords(node, prefix, result);
    return result;
  }
}

class SuffixTreeNode {
  children: Map<string, SuffixTreeNode> = new Map();
  start: number;
  end: number;
  suffixIndex: number = -1;

  constructor(start: number = -1, end: number = -1) {
    this.start = start;
    this.end = end;
  }

  get length(): number {
    return this.end - this.start + 1;
  }

  getEdgeString(text: string): string {
    return text.substring(this.start, this.end + 1);
  }
}

class SuffixTree {
  private root: SuffixTreeNode = new SuffixTreeNode();
  private text: string;
  private remainingSuffixCount: number = 0;
  private leafEnd: number = -1;
  private rootEnd: number | null = null;
  private splitEnd: number | null = null;
  private size: number = -1;

  constructor(text: string) {
    this.text = text + '$'; // 添加终止符
    this.size = this.text.length;
    this.buildSuffixTree();
  }

  private buildSuffixTree(): void {
    this.rootEnd = null;
    this.splitEnd = null;

    for (let i = 0; i < this.size; i++) {
      this.remainingSuffixCount++;
      this.leafEnd = i;
      this.extendSuffixTree(i);
    }
  }

  private extendSuffixTree(pos: number): void {
    let needParent: SuffixTreeNode | null = null;
    let needParentChar: string = '';

    while (this.remainingSuffixCount > 0) {
      if (this.activeLength === 0) {
        this.activeEdge = pos;
      }

      if (!this.activeNode.children.has(this.text[this.activeEdge])) {
        // 创建新叶子节点
        const leaf = new SuffixTreeNode(pos, this.leafEnd);
        this.activeNode.children.set(this.text[this.activeEdge], leaf);

        if (needParent) {
          needParent.children.set(needParentChar, this.activeNode);
          needParent = null;
        }
      } else {
        const next = this.activeNode.children.get(this.text[this.activeEdge])!;
        if (this.walkDown(next)) {
          continue;
        }

        if (this.text[next.start + this.activeLength] === this.text[pos]) {
          if (needParent && this.activeNode !== this.root) {
            needParent.children.set(needParentChar, this.activeNode);
            needParent = null;
          }
          this.activeLength++;
          break;
        }

        // 分裂节点
        const split = new SuffixTreeNode(next.start, next.start + this.activeLength - 1);
        this.activeNode.children.set(this.text[this.activeEdge], split);

        const leaf = new SuffixTreeNode(pos, this.leafEnd);
        split.children.set(this.text[pos], leaf);

        next.start += this.activeLength;
        split.children.set(this.text[next.start], next);

        if (needParent) {
          needParent.children.set(needParentChar, split);
        }
      }

      this.remainingSuffixCount--;

      if (this.activeNode === this.root && this.activeLength > 0) {
        this.activeLength--;
        this.activeEdge = pos - this.remainingSuffixCount + 1;
      } else if (this.activeNode !== this.root) {
        this.activeNode = this.activeNode.suffixLink!;
      }
    }
  }

  private activeNode: SuffixTreeNode = this.root;
  private activeEdge: number = -1;
  private activeLength: number = 0;

  private walkDown(curr: SuffixTreeNode): boolean {
    if (this.activeLength >= curr.length) {
      this.activeEdge += curr.length;
      this.activeLength -= curr.length;
      this.activeNode = curr;
      return true;
    }
    return false;
  }

  // 搜索子串
  search(pattern: string): boolean {
    let node = this.root;
    let i = 0;

    while (i < pattern.length) {
      if (!node.children.has(pattern[i])) {
        return false;
      }

      node = node.children.get(pattern[i])!;
      let j = node.start;

      while (i < pattern.length && j <= node.end) {
        if (pattern[i] !== this.text[j]) {
          return false;
        }
        i++;
        j++;
      }
    }

    return true;
  }

  // 查找所有出现位置
  findAllOccurrences(pattern: string): number[] {
    const positions: number[] = [];
    this.findOccurrences(this.root, pattern, 0, positions);
    return positions;
  }

  private findOccurrences(node: SuffixTreeNode, pattern: string, currentPos: number, positions: number[]): void {
    if (node.suffixIndex !== -1) {
      positions.push(node.suffixIndex);
    }

    for (const child of node.children.values()) {
      let i = 0;
      let j = child.start;

      while (i < pattern.length && j <= child.end) {
        if (pattern[i] !== this.text[j]) {
          break;
        }
        i++;
        j++;
      }

      if (i === pattern.length) {
        this.collectAllLeaves(child, positions);
      } else if (i > 0) {
        this.findOccurrences(child, pattern.substring(i), currentPos + i, positions);
      }
    }
  }

  private collectAllLeaves(node: SuffixTreeNode, positions: number[]): void {
    if (node.suffixIndex !== -1) {
      positions.push(node.suffixIndex);
    }

    for (const child of node.children.values()) {
      this.collectAllLeaves(child, positions);
    }
  }
}