shift table

Shift table，也称为移位表，是一种在字符串匹配算法中用来进行字符比较和移动的数据结构。在Boyer-Moore算法中，shift table用于快速地移动模式串，从而在文本串中快速地定位可能的匹配位置。

Shift table的构建基于模式串本身的特征，先对模式串的每个字符进行处理，计算出每个字符在模式串中最右边出现的位置，若字符在模式串中未出现，则表中对应位置为-1。然后根据已经处理好的字符信息，构建出整个shift table。

构建shift table的时间复杂度为O(m)，其中m为模式串的长度。在匹配过程中，使用shift table进行字符比较和移动，可以将匹配时间复杂度优化到O(n/m)，其中n为文本串的长度。

相关问题

shift table怎么画

Shift table是一种在字符串匹配算法中常用的数据结构，用于记录模式串中每个字符在发生不匹配时应该向右移动的距离。下面是一种常见的画shift table的方法：

1. 在表格的第一行中，写下模式串中的每个字符，按照从左到右的顺序排列。

2. 在表格的第二行中，从左到右记录每个字符在模式串中的最后一次出现的位置。如果一个字符在模式串中没有出现，则将其对应的位置设为-1。

3. 对于表格中的每个位置，计算该位置的值。如果该位置字符在模式串中出现过，则将该位置的值设为模式串中该字符在最后一次出现的位置与该位置之间的距离。否则，将该位置的值设为模式串长度。

下面是一个示例shift table的表格：

|字符|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|
|---|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|位置|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|
|值 |6|6|6|6|6|6|6|6|6|6|6 |6 |6 |6 |6 |6 |6 |6 |6 |6 |6 |6 |6 |6 |6 |6 |

在这个示例表格中，模式串为"hello world"，因此第一行中记录了模式串中的每个字符，第二行中记录了每个字符在模式串中的最后一次出现的位置，而第三行中的值则表示当发生不匹配时，模式串应该向右移动的距离。由于表格中所有位置的值均相同，因此在这种情况下不需要使用shift table。

layui table实现shift多选

要实现 shift 多选，需要监听鼠标按下和抬起事件，以及键盘按下和抬起事件。

首先，给每个需要选择的行添加一个 `data-index` 属性，表示该行的索引。

然后，在鼠标按下事件中记录下当前选中的行的索引（如果没有选中，则记录当前点击的行的索引），在鼠标抬起事件中记录结束选中的行的索引，计算出这两个行的之间的行，并将它们选中。

在键盘按下事件中，如果按下的是 shift 键，记录下当前选中的行的索引（如果没有选中，则记录当前焦点所在的行的索引），在键盘抬起事件中记录结束选中的行的索引，计算出这两个行的之间的行，并将它们选中。

以下是示例代码：

// 监听鼠标按下事件
table.on('checkboxMouseDown', function(obj){
  var index = obj.tr.data('index');
  if (!table.config.checkStatus.isAll) {
    table.checkStatus(obj.config.index).data.forEach(function(data){
      if (data.index === index) {
        data.mousedown = true;
      } else {
        data.mousedown = false;
      }
    });
  } else {
    table.checkStatus(obj.config.index).data.forEach(function(data){
      data.mousedown = false;
    });
  }
});

// 监听鼠标抬起事件
table.on('checkboxMouseUp', function(obj){
  var index = obj.tr.data('index');
  var checked = false;
  table.checkStatus(obj.config.index).data.forEach(function(data){
    if (data.index === index) {
      checked = true;
    } else if (data.mousedown) {
      data.checked = true;
    } else if (data.checked) {
      data.checked = false;
    }
  });
  if (checked) {
    table.checkStatus(obj.config.index).push(obj.data);
  } else {
    table.checkStatus(obj.config.index).remove(obj.data);
  }
});

// 监听键盘按下事件
table.on('checkboxKeyDown', function(obj){
  if (obj.event.keyCode === 16) {
    var index = obj.tr.data('index');
    if (!table.config.checkStatus.isAll) {
      table.checkStatus(obj.config.index).data.forEach(function(data){
        if (data.index === index) {
          data.keydown = true;
        } else {
          data.keydown = false;
        }
      });
    } else {
      table.checkStatus(obj.config.index).data.forEach(function(data){
        data.keydown = false;
      });
    }
  }
});

// 监听键盘抬起事件
table.on('checkboxKeyUp', function(obj){
  if (obj.event.keyCode === 16) {
    var index = obj.tr.data('index');
    var checked = false;
    table.checkStatus(obj.config.index).data.forEach(function(data){
      if (data.index === index) {
        checked = true;
      } else if (data.keydown) {
        data.checked = true;
      } else if (data.checked) {
        data.checked = false;
      }
    });
    if (checked) {
      table.checkStatus(obj.config.index).push(obj.data);
    } else {
      table.checkStatus(obj.config.index).remove(obj.data);
    }
  }
});