最小表示法 |
您所在的位置：网站首页 › shimly英语翻译 › 最小表示法 |
|
最小表示法定义 最小表示法是用于解决字符串最小表示问题的方法。 字符串的最小表示循环同构当字符串 中可以选定一个位置 满足 则称 与 循环同构 最小表示字符串 的最小表示为与 循环同构的所有字符串中字典序最小的字符串 simple 的暴力我们每次比较 和 开始的循环同构，把当前比较到的位置记作 ，每次遇到不一样的字符时便把大的跳过，最后剩下的就是最优解。 实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14int k = 0, i = 0, j = 1; while (k n && i n && j n) { if (sec[(i + k) % n] == sec[(j + k) % n]) { ++k; } else { if (sec[(i + k) % n] > sec[(j + k) % n]) ++i; else ++j; k = 0; if (i == j) i++; } } i = min(i, j); 1 2 3 4 5 6 7 8 9 10 11 12 13k, i, j = 0, 0, 1 while k n and i n and j n: if sec[(i + k) % n] == sec[(j + k) % n]: k += 1 else: if sec[(i + k) % n] > sec[(j + k) % n]: i += 1 else: j += 1 k = 0 if i == j: i += 1 i = min(i, j) 解释该实现方法随机数据下表现良好，但是可以构造特殊数据卡掉。 例如：对于 , 不难发现这个算法的复杂度退化为 。 我们发现，当字符串中出现多个连续重复子串时，此算法效率降低，我们考虑优化这个过程。 最小表示法算法核心考虑对于一对字符串 , 它们在原字符串 中的起始位置分别为 , 且它们的前 个字符均相同，即 不妨先考虑 的情况，我们发现起始位置下标 满足 的字符串均不能成为答案。因为对于任意一个字符串 （表示以 为起始位置的字符串，）一定存在字符串 比它更优。 所以我们比较时可以跳过下标 , 直接比较 这样，我们就完成了对于上文暴力的优化。 时间复杂度过程初始化指针 为 ， 为 ；初始化匹配长度 为 比较第 位的大小，根据比较结果跳转相应指针。若跳转后两个指针相同，则随意选一个加一以保证比较的两个字符串不同重复上述过程，直到比较结束答案为 中较小的一个实现 1 2 3 4 5 6 7 8 9 10 11int k = 0, i = 0, j = 1; while (k n && i n && j n) { if (sec[(i + k) % n] == sec[(j + k) % n]) { k++; } else { sec[(i + k) % n] > sec[(j + k) % n] ? i = i + k + 1 : j = j + k + 1; if (i == j) i++; k = 0; } } i = min(i, j); 1 2 3 4 5 6 7 8 9 10 11 12 13k, i, j = 0, 0, 1 while k n and i n and j n: if sec[(i + k) % n] == sec[(j + k) % n]: k += 1 else: if sec[(i + k) % n] > sec[(j + k) % n]: i = i + k + 1 else: j = j + k + 1 if i == j: i += 1 k = 0 i = min(i, j) 本页面最近更新：2023/10/4 21:50:08，更新历史发现错误？想一起完善？ 在 GitHub 上编辑此页！本页面贡献者：iamtwz, countercurrent-time, Early0v0, Enter-tainer, fjzzq2002, Ir1d, Junyan721113, karin0, ksyx, Menci, partychicken, shawlleyw, SukkaW, Suyun514, TrisolarisHD, Xeonacid本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |