string

August 18, 2025

模式串：abababzababab

第一步：一边遍历模式串，一边构造next数组。

next[i]表示字符串s[0:i+1]的前缀和后缀最大的公共长度
初始化j=0，i从1遍历到n-1。j的位置表示，此时s[:j]是公共前后缀
遍历时，如果此时有公共前后缀，不断比较s[i]和s[j]，一旦发现他们不同，则在循环中回退j，直到s[:j]成为公共前后缀。回退到此时的次长公共前后缀，将j移动到next[j-1]即可
再次比较s[i]和s[j]，如果相同，则移动j，并且为next[i]赋值

第二步：比较两个字符串
abeababeabf
abeabf

i表示当前找到的最优起始位置
j表示候选最优起始位置
k表示比较的偏移

s[i+k]==s[j+k], k+=1
s[i+k]<s[j+k]，此时可以更新j为最大起始位置，并且下一个候选者为max(j+1, i+k+1). 考虑字符串cacacb,i=0,j=2.
j+=1 肯定是没问题的，但是效率不高。s[i+k]<s[j+k],所以s[i+k]肯定不能是最优起始位置。
s[i+k]>s[j+k],j挑战失败，需要往后移动。说明之前比较的都相等，s[i]==s[j], …, s[i+k-1]==s[j+k-1]，而且s[i:i+k+1]肯定是降序的，不然i早就被替代了。写出一个例子dcbdcba,j=j+k+1

按频数从大到小排序，然后先填满偶数位，再填满奇数位

分块编码。

dummy_input = [“Hello”,“World”]

用前四位表示这一块的长度,然后加上这一块的实际内容

解码时，用 index追踪解码到哪里了，注意循环条件为while index<len(s)-3:

因为要确保当前循环包含了长度信息。