shift table怎么画
时间: 2024-05-13 08:03:00 浏览: 14
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。