求助关于最小表示法算法过程的问题
查看原帖
求助关于最小表示法算法过程的问题
931840
Grityn楼主2023/2/3 12:04

(下面提到的 stristr_i 表示以字符 sis_i 开始的循环同构串,nnss 的长度

我对此算法过程中两个指针 i,ji, j 的理解是:i,ji, j 表示 ss 的最小表示 一定存在于 stri,stri+1...strnstr_i, str_{i+1}...str_{n}, strj,strj+1..strnstr_j, str_{j+1}..str_n 中。这样理解可以解释当发现 si+ksj+ks_{i+k} \neq s_{j+k} 时(不妨设 si+k>sj+ks_{i+k} > s_{j+k})直接令 i=i+k+1i=i+k+1, 因为不影响候选答案集合。

不知道我这么理解对不对?

然后我有一个地方不太明白:

为什么当 i>ni>nj>nj>nstrmin(i,j)str_{min(i,j)} 就是答案?此时的候选答案集合是 strmin(i,j)...strnstr_{min(i,j)}...str_n,但怎么证明 strmin(i,j)str_{min(i, j)} 一定就是答案呢?

请各位大佬指教。

2023/2/3 12:04
加载中...