你说的 “字典序问题” —— NYOJ1542《最小字符串》，一般是要对字符串进行某种变换，最后得到字典序最小的结果。
题目背景（一般套路）
给定一个字符串，可以进行某种操作（比如交换、旋转、插入等），要求在所有可能的结果中找到字典序最小的字符串。
常见解题思路
- 贪心策略：优先选择字典序更小的字符或子串。
- 双指针：维护两个索引，比较两侧的字符，决定选择哪边字符放入结果。
- 使用栈：通过单调栈保持最小字典序。
- KMP / 最小表示法：对旋转类问题，找到最小表示。
假设题目是“给定字符串，允许从左边或右边选择一个字符拼接到结果字符串末尾，求最终字典序最小的字符串”。
典型解法代码（Java）
import java.util.Scanner;
public class NYOJ1542_MinString {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String s = sc.next();
char[] chars = s.toCharArray();
int i = 0, j = n - 1;
StringBuilder result = new StringBuilder();
while (i <= j) {
boolean leftIsSmaller = false;
int left = i, right = j;
while (left <= right) {
if (chars[left] < chars[right]) {
leftIsSmaller = true;
break;
} else if (chars[left] > chars[right]) {
leftIsSmaller = false;
break;
}
left++;
right--;
}
if (leftIsSmaller) {
result.append(chars[i++]);
} else {
result.append(chars[j--]);
}
}
System.out.println(result.toString());
sc.close();
}
}
代码说明
- 双指针分别从字符串两端开始比较。
- 当左侧字典序较小时，选择左端字符，否则选择右端字符。
- 直到指针相遇，构造出字典序最小的字符串。
好的！下面我帮你详细讲解这道题的双指针解法思路，为什么能保证得到字典序最小字符串，并给你附上 C++ 版本的完整代码示例。
题目简述（字典序最小字符串）
给定一个长度为 n 的字符串 s，你可以从字符串的两端取字符，依次组成一个新的字符串。
问：如何选择左右端字符，能使得最终组成的字符串字典序最小？
解题思路详解
为什么要比较两端字符？
- 我们每次只能从左端或右端取字符。
- 为了保证最终结果字典序最小，每次取字符时要优先选择更“字典序小”的那个端。
怎么比较？
- 如果左端字符比右端字符小，当然先取左端。
- 如果右端字符比左端字符小，先取右端。
- 如果两端字符相等怎么办？
这时不能简单只选一端，需要继续往内层比较对应的字符（即从左端向右，从右端向左）逐个比较，直到能判断哪边字典序更小，或者中间遇到相等的字符一直到两指针相遇。
算法核心
- 定义两个指针：
i（从左端开始），j（从右端开始） - 在
i <= j条件下：- 比较
s[i]和s[j] - 若不等，字典序小的端先取出字符，移动对应指针
- 若相等，则用两个临时指针
l = i,r = j向中间推进，比较s[l]和s[r]，判断哪边字典序更小
- 比较
- 将选择的字符依次拼接到结果字符串尾部
C++ 代码实现
#include <iostream>
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
string s;
cin >> s;
int i = 0, j = n - 1;
string result;
while (i <= j) {
bool takeLeft = false;
int l = i, r = j;
// 继续向中间比较，直到找到不等字符或者指针相遇
while (l <= r) {
if (s[l] < s[r]) {
takeLeft = true;
break;
} else if (s[l] > s[r]) {
takeLeft = false;
break;
}
l++;
r--;
}
if (takeLeft) {
result += s[i++];
} else {
result += s[j--];
}
}
// 输出结果，每行输出不超过80个字符（题目常见要求）
for (size_t k = 0; k < result.size(); k++) {
cout << result[k];
if ((k + 1) % 80 == 0) cout << '\n';
}
cout << '\n';
return 0;
}
总结
- 双指针向内推进，逐层比较，确保每次选字典序最小的边。
- 解决了两端字符相等时的判定问题。
- 代码效率 O(n2) 对一般数据量可接受，若数据量大可用字符串哈希等优化。
好嘞！我给你写一个详细注释的 C++ 代码版本，并加上用字符串哈希优化比较部分的思路，方便你理解和进一步优化。
带详细注释的 C++ 代码（普通双指针）
#include <iostream>
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
string s;
cin >> s;
int i = 0, j = n - 1;
string result;
while (i <= j) {
bool takeLeft = false;
int l = i, r = j;
// 向中间比较，判断选择左边还是右边
while (l <= r) {
if (s[l] < s[r]) {
// 左边字符更小，取左边
takeLeft = true;
break;
} else if (s[l] > s[r]) {
// 右边字符更小，取右边
takeLeft = false;
break;
}
// 相等时继续向中间比较
l++;
r--;
}
if (takeLeft) {
result += s[i++];
} else {
result += s[j--];
}
}
// 按题目常见要求，每80个字符换行
for (size_t k = 0; k < result.size(); k++) {
cout << result[k];
if ((k + 1) % 80 == 0) cout << '\n';
}
cout << '\n';
return 0;
}
字符串哈希优化思路
- 上述代码在最坏情况下两指针比较可能退化成 O(n2)
- 用 滚动哈希 或 双哈希 预处理字符串，使任意区间比较 O(1)
- 比较左侧子串 s[i..i+k] 和右侧子串 s[j−k..j] 时，通过哈希值判断大小，避免逐字符比较
哈希优化示例思路（伪代码）
// 预处理字符串哈希（前缀哈希）
// 比较s[i..i+len-1] 和 s[j-len+1..j]
// if hash(s[i..i+len-1]) < hash(s[j-len+1..j])
// 说明左侧字典序更小
// else
// 右侧更小或相等
// 利用二分查找最早不相等字符位置
好的！下面给你写一个基于 滚动哈希 + 二分比较 的 C++ 优化版本代码，解决两端字典序比较时的效率问题，适合大数据量。
代码说明
- 使用一个哈希函数（取模+乘基数）预处理字符串前缀哈希
- 利用二分查找比较两个子串的字典序
- 最终用双指针和哈希加速判断每次该选左边还是右边字符
完整代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100000 + 10;
const ll MOD1 = 1000000007;
const ll BASE1 = 131;
int n;
string s;
ll hash1[MAXN], power1[MAXN];
// 计算前缀哈希
void buildHash() {
hash1[0] = 0;
power1[0] = 1;
for (int i = 1; i <= n; i++) {
hash1[i] = (hash1[i - 1] * BASE1 + s[i - 1]) % MOD1;
power1[i] = (power1[i - 1] * BASE1) % MOD1;
}
}
// 取区间哈希值 [l,r]，1-based索引
ll getHash(int l, int r) {
return (hash1[r] - (hash1[l - 1] * power1[r - l + 1]) % MOD1 + MOD1) % MOD1;
}
// 比较区间 s[l1..r1] 和 s[l2..r2] 的字典序，返回 true 表示左边更小
bool lessOrEqual(int l1, int r1, int l2, int r2) {
int len = min(r1 - l1 + 1, r2 - l2 + 1);
int low = 0, high = len;
while (low < high) {
int mid = (low + high + 1) / 2;
if (getHash(l1, l1 + mid - 1) == getHash(l2, l2 + mid - 1)) {
low = mid;
} else {
high = mid - 1;
}
}
// low是最大公共前缀长度
if (low == len) {
// 短的字符串是另一个的前缀，短的字典序更小
return (r1 - l1) <= (r2 - l2);
}
// 比较第一个不同字符
return s[l1 + low - 1] < s[l2 + low - 1];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> s;
buildHash();
int i = 1, j = n; // 1-based索引
string result;
while (i <= j) {
if (lessOrEqual(i, j, n - j + 1, n - i + 1)) {
result.push_back(s[i - 1]);
i++;
} else {
result.push_back(s[j - 1]);
j--;
}
}
// 每80字符换行
for (int k = 0; k < (int)result.size(); k++) {
cout << result[k];
if ((k + 1) % 80 == 0) cout << '\n';
}
cout << '\n';
return 0;
}
关键点说明
- 预处理字符串
s的前缀哈希hash1[]和幂次数组power1[] getHash(l,r)用来快速计算子串哈希，时间 O(1)lessOrEqual(l1,r1,l2,r2)用二分查找最长公共前缀，再比较第一个不同字符，时间 O(logn)- 字符串索引均用1-based方便哈希计算，转换时注意减1访问字符串
s
这个方案能将原本 O(n2) 字符逐个比较降低到 O(nlogn)，适合大数据量处理。
好的！这里给你加上双哈希版本，防止哈希碰撞，代码结构和单哈希版本类似，只是多了第二套哈希参数和比较时两个哈希值都相等才判定相等。
双哈希版本 C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100000 + 10;
// 第一组哈希参数
const ll MOD1 = 1000000007;
const ll BASE1 = 131;
// 第二组哈希参数
const ll MOD2 = 1000000009;
const ll BASE2 = 137;
int n;
string s;
ll hash1_1[MAXN], power1_1[MAXN];
ll hash1_2[MAXN], power1_2[MAXN];
// 计算前缀哈希
void buildHash() {
hash1_1[0] = 0; power1_1[0] = 1;
hash1_2[0] = 0; power1_2[0] = 1;
for (int i = 1; i <= n; i++) {
hash1_1[i] = (hash1_1[i - 1] * BASE1 + s[i - 1]) % MOD1;
power1_1[i] = (power1_1[i - 1] * BASE1) % MOD1;
hash1_2[i] = (hash1_2[i - 1] * BASE2 + s[i - 1]) % MOD2;
power1_2[i] = (power1_2[i - 1] * BASE2) % MOD2;
}
}
// 取区间哈希值 [l,r]，1-based索引
pair<ll,ll> getHash(int l, int r) {
ll res1 = (hash1_1[r] - (hash1_1[l - 1] * power1_1[r - l + 1]) % MOD1 + MOD1) % MOD1;
ll res2 = (hash1_2[r] - (hash1_2[l - 1] * power1_2[r - l + 1]) % MOD2 + MOD2) % MOD2;
return {res1, res2};
}
// 比较区间 s[l1..r1] 和 s[l2..r2] 的字典序，返回 true 表示左边更小
bool lessOrEqual(int l1, int r1, int l2, int r2) {
int len = min(r1 - l1 + 1, r2 - l2 + 1);
int low = 0, high = len;
while (low < high) {
int mid = (low + high + 1) / 2;
if (getHash(l1, l1 + mid - 1) == getHash(l2, l2 + mid - 1)) {
low = mid;
} else {
high = mid - 1;
}
}
if (low == len) {
return (r1 - l1) <= (r2 - l2);
}
return s[l1 + low - 1] < s[l2 + low - 1];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> s;
buildHash();
int i = 1, j = n;
string result;
while (i <= j) {
if (lessOrEqual(i, j, n - j + 1, n - i + 1)) {
result.push_back(s[i - 1]);
i++;
} else {
result.push_back(s[j - 1]);
j--;
}
}
for (int k = 0; k < (int)result.size(); k++) {
cout << result[k];
if ((k + 1) % 80 == 0) cout << '\n';
}
cout << '\n';
return 0;
}
说明
- 双哈希避免单哈希偶发冲突，安全性更高
- 时间复杂度 O(nlogn)，适合大数据量
- 代码结构清晰易改
发表回复