1. 项目概述与核心价值最近在准备华为OD机试的朋友应该对字符串处理类的题目不陌生。这类题目看似基础但往往是拉开分数差距的关键。今天要拆解的这道“第K个字母在原来字符串的索引”就是一个非常典型的例子。它考察的不仅仅是简单的字符串查找更涉及对字符串变换、索引映射逻辑的深刻理解以及在不同编程语言C、Java、Python、C、JS下如何高效、优雅地实现。如果你正在刷题或者对算法竞赛感兴趣这道题能帮你很好地巩固字符串操作和数学推导能力。简单来说题目会给你一个原始字符串和一个经过某种规则变换后的新字符串然后问你新字符串中的第K个字符在原始字符串中位于哪个位置这听起来有点像“寻宝游戏”你需要根据变换规则反向推导出原始坐标。这类问题在机试中频繁出现因为它能有效检验候选人的逻辑思维、代码实现和边界条件处理能力。接下来我会从思路分析、代码实现到避坑指南带你完整走一遍。2. 问题深度解析与思路构建2.1 题目场景还原与抽象建模首先我们需要把模糊的题目描述具体化。通常这类题目的核心变换规则是“循环移位”或“基于某种排序的重排”。为了进行通用性分析我们假设一个最常见的场景原始字符串S的长度为n。经过变换后得到了一个新的字符串S‘。已知S‘是S的所有循环同构字符串按字典序排序后的连接。这是什么意思呢举个例子假设原始字符串S “abc”。它的所有循环同构字符串即每次将第一个字符移到末尾有“abc”,“bca”,“cab”。将这些字符串按字典序排序“abc”,“bca”,“cab”。将它们连接起来得到新字符串S‘ “abcbca cab”(这里为了清晰加了空格实际没有)。现在的问题是给定S‘和S‘中的一个位置K(从0或1开始索引需确认)要求找出S‘[K]这个字符在原始字符串S中的位置。另一种常见变体是S‘为S的所有后缀按字典序排序后的连接即后缀数组的连接。解题的核心思路是相通的建立从新字符串索引到原始字符串索引的映射关系。2.2 核心思路推导数学映射法暴力方法是不可取的因为字符串长度可能很大。我们需要找到映射的数学规律。以“循环同构排序连接”为例设原始字符串S长度为n。新字符串S‘的长度为n * n因为它由n个长度为n的字符串连接而成。这n个子串就是S的n个循环同构串。排序后每个子串都对应一个“起始偏移”offset(0 offset n)表示这个子串是从S的第offset个字符开始循环取得的。关键推导K是S‘中的索引。我们可以通过K / n得到K所在的排序后子串的序号记作block_id。通过K % n得到K在该子串内的局部偏移记作local_offset。现在我们知道S‘[K]位于第block_id个子串的第local_offset个位置。这个子串是原始字符串S以某个offset为起点的循环串。因此该字符在原始串S中的索引original_index为original_index (offset local_offset) % n问题转化为如何根据block_id求出对应的offset这就是本题的算法核心。我们需要知道排序后第block_id个子串对应的原始起始偏移offset是多少。这等价于求取字符串S的循环同构串按字典序排序后的顺序数组通常称为“循环后缀数组”或“BWT变换中的轮转排序”。2.3 算法选择与复杂度分析求解排序顺序有两种主流思路直接构造与排序生成S的所有n个循环子串。对这些子串进行排序并记录每个子串的原始offset。排序后offset数组就是我们要的映射关系。时间复杂度生成子串 O(n²)排序 O(n² log n)。当n较大时例如 n10^5完全不可行。后缀数组/扩展KMPZ算法优化这是处理此类问题的标准高效算法。我们可以将循环串的问题转化为普通字符串问题。技巧构造一个新字符串T S S。这样S的每一个长度为n的循环子串都对应T的一个长度为n的子串。问题转化为对T的所有长度为n的子串起始位置为 0 到 n-1按字典序排序。这可以通过求T的后缀数组Suffix Array来高效解决。因为对后缀排序后我们只需要关注那些起始位置小于n的后缀并且只比较前n个字符。使用倍增法或SA-IS算法构建后缀数组时间复杂度可以做到 O(n log n) 甚至 O(n)。得到后缀数组sa后筛选出sa[i] n的那些位置它们就是按字典序排序后的循环子串的起始偏移offset其顺序就是block_id。对于机试场景如果n的范围在 10^3 到 10^4 量级方法1在部分语言中可能勉强能过尤其是Python需要谨慎。但如果n达到 10^5必须使用方法2。华为OD的题目通常会设置合适的数据范围来区分不同水平的解法。注意在具体实现时务必首先明确题目给出的变换规则。上述分析基于“循环同构排序”如果规则是“后缀排序”则构造T S即可无需拼接其他思路类似。务必仔细阅读题目的输入输出描述和样例。3. 多语言代码实现与细节剖析理解了核心算法我们来看代码实现。我会分别用 C, Java, Python, C 和 JavaScript 给出基于直接构造与排序方法的代码因其更直观适合在机试中快速实现前提是数据范围允许并附上关键注释。同时我会指出每种语言实现时的注意事项和性能瓶颈。3.1 C 实现C 得益于 STL 的强大实现起来非常简洁高效。#include iostream #include string #include vector #include algorithm using namespace std; int main() { string s; long long k; // 使用long long防止大数溢出 cin s k; int n s.size(); // 注意题目索引可能从1开始这里假设k是从1开始的先转为0-based k--; // 1. 生成所有循环子串及其起始偏移 vectorpairstring, int rotations; // pair子串, 原始偏移 for (int i 0; i n; i) { string rot s.substr(i) s.substr(0, i); rotations.emplace_back(rot, i); } // 2. 按字典序排序子串 sort(rotations.begin(), rotations.end()); // 3. 计算K所在的块(block_id)和块内偏移(local_offset) long long block_id k / n; int local_offset k % n; // 4. 找到第block_id个子串的原始偏移offset int original_offset rotations[block_id].second; // 5. 计算原始字符串中的索引 int original_index (original_offset local_offset) % n; // 输出如果题目要求1-based索引则1 cout original_index endl; // 假设输出0-based索引 // cout original_index 1 endl; // 如果要求1-based索引 return 0; }C实现要点substr方法s.substr(i)获取从i到末尾的子串s.substr(0, i)获取前i个字符。拼接起来就得到了循环子串。emplace_back在容器尾部直接构造元素比push_back(make_pair(...))更高效。排序复杂度sort是 O(n log n) 比较但每次比较的是长度为n的字符串因此实际复杂度为 O(n² log n)。这是主要性能瓶颈。大数处理k可能很大要用long long。k/n和k%n也要用long long类型计算避免中途溢出。3.2 Java 实现Java 的实现思路类似但要注意字符串操作和排序的细节。import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); String s scanner.next(); long k scanner.nextLong(); // 使用long int n s.length(); k--; // 转为0-based索引 // 1. 生成所有循环子串和偏移 ListPair rotations new ArrayList(); for (int i 0; i n; i) { String rot s.substring(i) s.substring(0, i); rotations.add(new Pair(rot, i)); } // 2. 排序 rotations.sort(Comparator.comparing(o - o.str)); // 3. 计算block_id和local_offset long blockId k / n; int localOffset (int)(k % n); // k%n 结果一定小于n可以转int // 4. 获取原始偏移 int originalOffset rotations.get((int)blockId).idx; // 5. 计算原始索引 int originalIndex (originalOffset localOffset) % n; System.out.println(originalIndex); // 输出0-based索引 // System.out.println(originalIndex 1); // 输出1-based索引 scanner.close(); } static class Pair { String str; int idx; Pair(String str, int idx) { this.str str; this.idx idx; } } }Java实现要点substring(i)Java 的substring是前闭后开区间s.substring(i)表示从i到末尾。排序使用List.sort(Comparator)并传入一个按str字段比较的Comparator代码简洁。类型转换blockId是long型但List.get()需要int索引。因为blockId k / n且k n*n所以blockId n对于n在 int 范围内的情况强制转换(int)blockId是安全的。这是一个容易忽略的细节。类设计内部静态类Pair用于存储子串和偏移比使用Map.Entry更清晰。3.3 Python 实现Python 代码最为简短但需要特别注意性能问题。def main(): s input().strip() k int(input().strip()) n len(s) k - 1 # 转为0-based索引 # 1. 生成所有循环子串和偏移 rotations [] for i in range(n): rot s[i:] s[:i] rotations.append((rot, i)) # 2. 按子串字典序排序 rotations.sort(keylambda x: x[0]) # 3. 计算block_id和local_offset block_id k // n local_offset k % n # 4. 获取原始偏移 original_offset rotations[block_id][1] # 5. 计算原始索引 original_index (original_offset local_offset) % n print(original_index) # 输出0-based索引 # print(original_index 1) # 输出1-based索引 if __name__ __main__: main()Python实现要点切片操作s[i:]和s[:i]是 Python 字符串切片的优势非常高效且语法简洁。排序list.sort(keylambda x: x[0])指定按照元组第一个元素即子串进行排序。整除Python 3 中//是整数除法/是浮点除法这里必须用//。性能警告这是 Python 实现最大的坑。当n较大时比如超过2000生成n个长度为n的字符串内存占用约为 O(n²)很容易导致内存超限MLE。排序比较字符串也是 O(n² log n) 的复杂度在 n5000 时就可能超时。因此Python 解法必须考虑优化不能直接套用此模板应对大数据。优化方向是使用后缀数组SA或仅存储偏移量并在比较时进行虚拟比较。3.4 C 语言实现C 语言的实现需要手动管理内存和字符串比较更为底层。#include stdio.h #include stdlib.h #include string.h typedef struct { char* str; // 指向循环子串的指针实际上是原字符串的重新解释 int offset; } Rotation; // 比较函数用于qsort int cmp(const void* a, const void* b) { Rotation* ra (Rotation*)a; Rotation* rb (Rotation*)b; return strcmp(ra-str, rb-str); } int main() { char s[100005]; // 根据题目可能的最大长度调整数组大小 long long k; scanf(%s %lld, s, k); int n strlen(s); k--; // 转为0-based // 1. 分配内存并生成Rotation结构体数组 Rotation* rotations (Rotation*)malloc(n * sizeof(Rotation)); for (int i 0; i n; i) { rotations[i].offset i; // 关键我们不实际复制字符串而是让str指向一个“虚拟”的循环起点。 // 这需要自定义比较函数但这里为了简单我们先分配新字符串。 // 注意这种方法在n很大时同样有内存问题。优化方法见下文分析。 rotations[i].str (char*)malloc((n 1) * sizeof(char)); // 构造循环子串 s[i..n-1] s[0..i-1] int idx 0; for (int j i; j n; j) rotations[i].str[idx] s[j]; for (int j 0; j i; j) rotations[i].str[idx] s[j]; rotations[i].str[idx] \0; // 字符串结束符 } // 2. 排序 qsort(rotations, n, sizeof(Rotation), cmp); // 3. 计算block_id和local_offset long long block_id k / n; int local_offset k % n; // 4. 获取原始偏移 int original_offset rotations[block_id].offset; // 5. 计算原始索引 int original_index (original_offset local_offset) % n; printf(%d\n, original_index); // 输出0-based索引 // 6. 释放内存 for (int i 0; i n; i) { free(rotations[i].str); } free(rotations); return 0; }C语言实现要点与陷阱内存管理必须为每个Rotation结构体和其内部的str分配内存并在最后释放否则会造成内存泄漏。这是 C 语言编程的基本功但在紧张的机试中容易忘记。性能与内存上述代码为每个循环子串都复制了一份完整的字符串内存消耗 O(n²)与 Python 版本存在同样的问题且 C 语言中频繁的malloc和free也会带来开销。优化策略更优的 C 语言实现不应复制字符串。可以只存储偏移量offset并编写一个自定义的比较函数cmp。在这个cmp函数中比较两个偏移量i和j对应的循环子串时通过原字符串s和长度n进行“虚拟比较”。例如比较s[i]与s[j]如果相等则比较s[(i1)%n]与s[(j1)%n]以此类推。这样可以将空间复杂度降至 O(n)但比较函数的复杂度为 O(n)使得排序的总复杂度为 O(n² log n)时间换空间。字符串结束符手动构造字符串时千万别忘了在末尾添加\0。3.5 JavaScript (Node.js) 实现JavaScript 在算法竞赛中如使用 Node.js 环境也越来越常见。const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); let inputLines []; rl.on(line, (line) { inputLines.push(line.trim()); if (inputLines.length 2) { main(); rl.close(); } }); function main() { const s inputLines[0]; let k BigInt(inputLines[1]); // 使用BigInt处理大整数 const n s.length; k--; // 转为0-based索引 // 1. 生成所有循环子串和偏移 const rotations []; for (let i 0; i n; i) { const rot s.slice(i) s.slice(0, i); rotations.push([rot, i]); } // 2. 排序 rotations.sort((a, b) a[0].localeCompare(b[0])); // 3. 计算block_id和local_offset const blockId Number(k / BigInt(n)); // BigInt除法结果转为Number const localOffset Number(k % BigInt(n)); // 4. 获取原始偏移 const originalOffset rotations[blockId][1]; // 5. 计算原始索引 const originalIndex (originalOffset localOffset) % n; console.log(originalIndex); // 输出0-based索引 }JavaScript实现要点大整数处理JavaScript 的Number类型有安全整数范围2^53-1。如果k可能很大必须使用BigInt。BigInt的运算/,%结果也是BigInt需要转换为Number用于数组索引。字符串切片slice方法与 Python 类似非常方便。排序比较字符串比较不能直接用或对数组排序需要使用localeCompare方法或在sort回调中显式比较。性能同样存在 O(n²) 内存和 O(n² log n) 时间复杂度的瓶颈。在 V8 引擎下对于 n5000 的用例也可能超时或内存不足。4. 高效算法优化后缀数组解法详解对于大数据范围n 5000上述直接排序的方法在时间和空间上都不够用。我们必须采用更高效的后缀数组Suffix Array算法。这里以“循环同构排序”为例给出 C 的优化解法思路。核心思想是构建字符串T S S的后缀数组然后取所有起始位置在[0, n-1]范围内的后缀并根据它们的前n个字符进行排序。#include iostream #include string #include vector #include algorithm using namespace std; // 使用倍增法构建后缀数组 (O(n log n)) vectorint buildSuffixArray(const string t) { int n t.size(); vectorint sa(n), rank(n), tmp(n); int k; // 初始排序按单个字符 for (int i 0; i n; i) { sa[i] i; rank[i] t[i]; // 直接使用字符ASCII码作为第一关键字 } // 倍增排序 for (k 1; k n; k * 2) { // 自定义比较函数先比较第一关键字再比较第二关键字 auto cmp [](int a, int b) { if (rank[a] ! rank[b]) return rank[a] rank[b]; // 处理第二关键字如果越界则赋值为-1表示空字典序最小 int ra (a k n) ? rank[a k] : -1; int rb (b k n) ? rank[b k] : -1; return ra rb; }; sort(sa.begin(), sa.end(), cmp); // 重新计算排名 tmp[sa[0]] 0; for (int i 1; i n; i) { tmp[sa[i]] tmp[sa[i-1]] (cmp(sa[i-1], sa[i]) ? 1 : 0); } rank.swap(tmp); } return sa; } int main() { string s; long long k; cin s k; k--; // 0-based int n s.size(); // 构建扩展字符串 T S S string t s s; // 构建后缀数组 vectorint sa buildSuffixArray(t); // 收集所有起始位置在 [0, n-1] 的后缀它们对应S的循环子串 vectorint offsets; // 按字典序存储循环子串的起始偏移 for (int i 0; i sa.size(); i) { if (sa[i] n) { offsets.push_back(sa[i]); } // 如果我们已经收集了n个就可以提前退出 if (offsets.size() n) break; } // 后续计算与之前相同 long long block_id k / n; int local_offset k % n; int original_offset offsets[block_id]; int original_index (original_offset local_offset) % n; cout original_index endl; return 0; }后缀数组解法的优势时间复杂度倍增法为 O(n log n)SA-IS 算法可达 O(n)。远优于 O(n² log n)。空间复杂度主要消耗在于后缀数组sa和排名数组rank均为 O(n)。避免了存储所有子串的 O(n²) 内存。适用性此方法是解决此类字符串排序、索引映射问题的标准且强大的工具。实现难点后缀数组构建理解倍增法的“双关键字排序”思想是关键。代码中通过rank数组记录当前长度下的排名每次倍增后利用上一轮的排名快速计算新的双关键字。边界处理在比较第二关键字时对于ak n的情况我们将其排名设为-1确保空后缀排在前面这是正确的。去重T的长度是2n其后缀数组有2n个元素。我们只关心那些起始位置在原始字符串长度n以内的后缀因为它们对应长度为n的循环子串。5. 常见陷阱、调试技巧与扩展思考5.1 机试中的常见“坑点”索引基准问题题目和样例通常会说清楚索引是从0开始还是从1开始。输入的位置K和最终输出的答案必须统一基准。我建议在内部全部转为0-based进行计算最后根据要求输出。上面的代码都遵循了这个原则。大数溢出K可以非常大最大可能为n*n对于n10^5K可达10^10。必须使用long long(C/C)、long(Java)、int64或BigInt(JS) 来存储。在 C/C 中int类型的n与long long类型的k进行k / n运算时要确保n也被提升为long long类型或者直接使用1LL * n。内存与时间限制这是 Python 和 JavaScript 解法的“杀手”。务必在动手前评估数据范围。如果n超过 2000直接构造所有子串的方法就非常危险。必须考虑后缀数组等优化方案。字符串包含空格或其他字符题目输入有时会包含空格。使用cin s(C) 或scanner.next()(Java) 会以空格为分隔符。如果字符串可能包含空格必须使用getline(cin, s)或scanner.nextLine()。这是一个经典的“Presentation Error”错误来源。多组测试数据题目可能包含多组测试用例。代码框架需要能够循环读取直到文件结束EOF。例如在 C 中使用while(cin s k)。5.2 调试与验证技巧小数据验证用“abc”这样的小字符串手动推导所有循环串、排序结果然后验证程序对于不同K的输出是否正确。随机数据对拍编写一个暴力但正确的程序例如直接构造出新字符串S‘然后查找S‘[K]对应的原始字符。用随机生成的小规模数据n10运行你的高效算法和暴力算法对比结果是否一致。这是发现边界错误最有效的方法。输出中间变量在调试时可以打印出rotations数组排序后、offsets数组等观察其顺序是否符合预期。关注排序稳定性如果两个循环子串完全相同例如S“aaa”它们的排序顺序可能任意。但这不影响最终结果吗会影响因为block_id对应了排序后的第几个子串。如果顺序不定original_offset就可能不同进而导致original_index不同。这是一个非常重要的边界情况题目必须保证S的所有循环子串互不相同或者明确定义了相同子串的排序规则通常按原始偏移排序。如果题目没有说明你需要向考官确认或者在代码中通过稳定排序或比较原始偏移来消除二义性。5.3 问题扩展与变体后缀数组变体如果题目中的S‘是S的所有后缀排序后连接而成那么解法更简单。只需构建S本身的后缀数组sa则offsets数组就是sa本身因为每个后缀的起始位置就是偏移。计算original_index的公式变为original_index offsets[block_id] local_offset当然要确保local_offset不会超出该后缀的长度在这个问题中每个“块”长度不同需要额外处理。第K小子串问题这是一个更经典的问题给定字符串求其所有不同子串中字典序第K小的那个。这需要结合后缀数组和高度数组lcp来计算每个后缀贡献了多少个新的、不同的子串然后进行二分查找。其思想与本问题有相通之处。在线查询如果有多组不同的K需要查询我们可以在预处理阶段O(n log n)构建好offsets数组之后每次查询都可以在 O(1) 时间内完成。这体现了预处理的价值。这道“第K个字母在原来字符串的索引”题目就像一把钥匙打开了一类字符串索引映射问题的大门。它的价值不在于背下代码而在于理解其从暴力模拟到数学映射再到高效算法优化的思维链条。在机试或面试中即使你最终没有时间写出完美的后缀数组如果能清晰地阐述这种优化思路也足以展现你的算法功底。在实际编码时先从清晰的暴力思路写起确保逻辑正确再根据数据范围思考优化这才是稳健的解题之道。