企业官网建设流程全解析

在洛谷字符串专题刷了快两个月，从一开始靠暴力遍历被卡到怀疑人生，到现在能一口气理清哈希、KMP、Trie、AC自动机这些思路，算是摸到了一点门道。这篇文章算是我这段时间“刷题有感”的整理，也是一份面向新人的避坑指南。如果你正打算啃字符串这块硬骨头，或者已经刷了十几道却总觉得套路不熟，这篇应该能给你一些参考。

字符串题在洛谷上属于“看起来简单，做起来破防”的类型。不做前缀和、不手写KMP，纯靠语言自带函数去暴力匹配，大概率卡时间；可一旦你学会把字符串当成“序列”来看，很多题其实都是固定模板加一点点变式。这篇不算教程，更多是我踩过坑、换过思路之后沉淀下来的经验，尽量说人话，把“为什么这么做”讲清楚。

1. 先想明白字符串题到底在考什么

1.1 别把字符串当普通数组去硬算

我刚开始刷字符串题时，脑子里只有一种思路：把每个字符放进数组，需要匹配就一层层循环扫。这在小数据量下确实能过，比如一个字符串长度只有几百，两个for循环可能还撑得住。但洛谷的字符串题经常是10^5甚至10^6级别的输入，这种数据的匹配操作如果还是O(n*m)，跑起来就是灾难。

后来我意识到，字符串题考的不是“你会不会遍历字符”，而是“你能不能把字符串之间的大量重复比较压缩掉”。正常情况下，我们要处理的无非是这几类需求：判断两个子串是否相等、找某个模式串在主串中出现的位置、统计一堆模式串出现了多少次、按前缀分类等等。这些需求本质上都是在问“我怎么避免重复扫描已经看过的字符”。

所以心态要先转换。字符串是数组，但你不能只拿它当数组用。它更像是“自带某种结构”的序列，你需要找到一种方式，让匹配的信息可以被复用。比如KMP里那个next数组，就是把这个思想体现得特别典型的一个例子——你失配之后不需要从头再来，因为有next数组帮你记住了当前位置之前的最长前缀信息。理解这个本质，比记住模板重要得多。

1.2 洛谷里字符串题常见“长相”

在洛谷刷题页里，字符串标签下常见的题目大概能分成几类，这里我按实际刷题时遇见的频率大致排一排：

• 字符串匹配类：给你一个文本串和一个模式串，问模式串在文本串中出现多少次/哪里出现，这种题基本就是KMP的练手场。
• 多模式串匹配类：给你一堆模式串和一个文本串，问每个模式串出现了几次。这类题直接上AC自动机，不会的话就只能靠哈希硬凑。
• 前缀相关类：求公共前缀、某个字符串是否是一个集合里另一个串的前缀等，Trie树是首选。
• 子串相等/回文类：经常要快速判断两个子串是否相等，或者求回文子串数目，这种用字符串哈希加二分/枚举会方便很多。
• 字典序/排序类：有时候只是排序，但排序规则特别怪异，需要自定义比较函数，这也会牵扯到一些字符串处理细节。

这几类不是完全独立，比如AC自动机本质上就是Trie树加KMP的失配指针。你一个人单独只学哈希也能做不少题，但如果只懂哈希，遇到AC自动机那种“每个模式串出现次数”的题就会很难受。所以我的经验是：不要只抓一个点，要把这几个核心算法串起来理解。

2. 刷题之前的准备工作：基本功决定你能走多远

2.1 语言与输入输出：选对了能少挨几次TLE

字符串题非常讲求输入输出效率。如果你用C++，建议统一关闭同步流，不然cin遇上10^6级别的字符串输入，常常会被卡掉长时间限制。我习惯在main开头写这行：

ios::sync_with_stdio(false); cin.tie(nullptr);

这两行的作用是让C++的输入输出不再和C标准IO同步，速度能快不少。注意用了这个之后，就不要再混用printf和cout了，否则顺序可能乱。

如果你偏爱scanf/printf，也不是不行，但字符串读入时要特别小心换行符。比如你要读一串可能带有空格的字符串，用scanf("%s")只能读到空白符之前，如果题目说“可能包含空格”，那就要用cin.getline或者getline来读。Python则简单一些，input()会帮你处理换行，但速度较慢，遇到大数据量最好改用sys.stdin.buffer.read()一次性读进来再split。

这些输入输出细节看着不起眼，但其实很多WA和TLE都是在这里翻车的。尤其是字符串题经常有一整行没用的前置信息、多个测试用例需要循环读入，如果读错要么多读了空行，要么少读了数据，后面算法写得再漂亮也白搭。

2.2 一套稳定不翻车的模板：别每次重写

刷字符串题和刷数学题不一样，算法模板一定要用“肌肉记忆”存下来，不能每次现场推。我自己的经验是：每种核心算法维护一个最小可用的模板，放在本地代码库里，考前或刷题时直接调出来抄。这里尤其推荐把字符串哈希和KMP做成模板，因为它们的代码很短，但细节很多。

字符串哈希模板的核心是“把字符串看成一个大整数，用前缀哈希相减判断子串相等”。我一般用双哈希或者带大质数的单哈希，代码大致长这样：

typedef unsigned long long ull; const ull base = 131; const int N = 100005; ull h[N], p[N]; char s[N]; void init() { p[0] = 1; for (int i = 1; i <= strlen(s); i++) { h[i] = h[i-1] * base + s[i-1]; p[i] = p[i-1] * base; } } ull getHash(int l, int r) { // l,r从1开始 return h[r] - h[l-1] * p[r-l+1]; }

这段代码里最容易写错的点在于下标。我习惯让哈希数组的下标从1开始，而原字符串char数组从0开始，这样在for循环里要把s[i-1]映射到h[i]。如果你从0开始处理，查询区间也要跟着改，很容易混乱。

KMP模板我一般只背一个失配函数，不用写多版本：

void getNext(string p) { int n = p.size(); vector<int> ne(n); for (int i = 1, j = 0; i < n; i++) { while (j > 0 && p[i] != p[j]) j = ne[j-1]; if (p[i] == p[j]) j++; ne[i] = j; } }

这里的ne[i]表示“以i结尾的前缀长度是多少”，也就是说如果主串在i位置失配了，模式串指针应该跳到ne[i-1]。实际匹配时再把这个next数组用起来。这类模板不写一次就背住，很容易把边界漏了。

2.3 提前算好复杂度：别等TLE才后悔

刷题最怕的就是“惯性写暴力”。看到遍历两个数组比较子串相等的题，第一反应是双循环枚举子串起点终点，复杂度O(n^2)，然后可能直接TLE。其实所有字符串算法题，都应该先看数据范围再选算法。比如：

• n <= 1000：暴力循环也许可以，但要算清常数。
• n <= 10^5：O(n log n)左右可接受，KMP/哈希/Trie都适合。
• n <= 10^6：通常需要O(n)算法，有些O(n log n)会因为常数大被卡。

这里的“常数”很关键。比如哈希的查询虽然是O(1)，但每次要算一个getHash()，如果调用次数达到n^2，那照样超时。所以要学会估算调用次数。比如你枚举所有子串判断回文，总子串数O(n^2)，就算哈希查询O(1)也完蛋。这种时候要另找优化，比如Manacher或者中心扩展。判断复杂度这一步，不能省。

3. 核心套路逐个拆解：哈希、KMP、Trie与AC自动机

3.1 字符串哈希：把相等判断变成数值比较

字符串哈希在洛谷字符串题里是硬通货。很多题不需要你会KMP，只要你会判断两个子串“是否相等”就够了。哈希就是干这个的，它把一段字符串映射成一个整数，比较时比数字大小，O(1)搞定。

但里面有几件事很容易踩坑。

第一，冲突问题。单模数很容易被构造出来的数据卡掉。洛谷的题不一定会故意卡哈希，但竞赛环境里“不放心”是常态。我用的哈希模数一般是1e9+7或1e9+9，或者干脆用unsigned long long自然溢出。自然溢出的意思是让数值自动模2^64，速度很快，但碰撞概率比大质数稍高，不过大多数题够用。如果你追求稳，那就双哈希：两个不同模数分别算，两个都相等才认为相等。这样冲突概率基本可以忽略。

第二，基数的选择。常见的base可以是131、13331、233等。理论上base要大于字符集大小，并和模数互质。用131是我个人的习惯，不容易出问题。

第三，下标混乱。像上一节说的，哈希前缀和的下标起始非常容易出错。我的建议是统一“从1开始”代表前缀长度。读入字符串后，在init时用for (int i = 0; i < n; i++) h[i+1] = h[i] * base + s[i];，这样从1到n都是完整的前缀哈希，查询时直接用getHash(l, r)，l和r是两个1-based的位置。多写几次，形成肌肉记忆。

哈希的经典应用不只是字面意思的“相等判断”，还可以结合二分解决最长回文子串、最长公共前缀、任意子串比较等等。用哈希求最长公共前缀时，你可以二分长度，如果前缀哈希相等，就代表这一段相同。这里哈希的优势就体现出来了：O(log n)一次，不用真的扫字符。

3.2 KMP：用一个next数组干掉重复匹配

KMP是我一开始最头疼的算法，因为next数组的理解和构造总有一种“道理都懂，代码就错”的感觉。后来我换了个角度理解：模式串在匹配过程中，如果主串第i个字符和模式串第j个字符不相等，那我们不把模式串整体后移一位再从0开始比，而是把模式串指针跳到“已经匹配好的前缀中，最长公共前后缀的末尾”，这样主串指针不用回头，模式串指针也不至于回到开头。next数组就是“匹配失败后，模式串指针应该跳到哪”的提前表。

洛谷里很多字符串匹配题，裸KMP能过。但我还要多说一句：别只会写KMP的匹配而不会求出现次数。出现次数分两种：一种是不重叠计数，匹配成功一次就把指针拉到0继续扫；另一种是重叠计数，匹配成功后指针要跳到next[j-1]，这样能继续发现重叠匹配。题目会明确要求，还是重叠这种更常见。我经常忘了这层，导致结果少算。

写KMP时建议把模式串和主串都从0开始存，然后用同样的下标规则写next函数。比如getNext里面把ne[i]定义为：长度为i的前缀子串中，最长相等前后缀的长度（不含整个串本身）。匹配时维护j为当前模式串匹配到的长度，遍历主串每个字符t[i]，如果失配就j = ne[j-1]，若匹配则j++，当j == m时找到一个匹配点。

3.3 Trie：把一堆字符串收进一棵树

Trie字典树解决的是“前缀相关”问题，以及“某个字符串是否存在/是否出现过多次”的计数问题。它的核心思想非常直白：把所有字符串的公共前缀压缩成一条共享路径。比如你有abc和abd两个串，插入的时候前两个字符ab共用节点，只在第三个字符分开。

在洛谷刷Trie题，我最常写的结构体是：

struct TrieNode { int nxt[26]; int cnt; TrieNode() { memset(nxt, 0, sizeof(nxt)); cnt = 0; } }; vector<TrieNode> tr;

每次插入就从根节点开始，按字符找下一个节点。如果节点不存在就新建。统计每个节点经过次数还是结尾次数，要看题目要求。比如问“有多少个字符串以某字符串为前缀”，你只需要在插入时经过每个节点都计数；问“这个词有没有出现过/出现几次”，就要在结尾位置加一。

Trie写起来不难，但容易爆内存。因为数组开小了可能RE，开大了可能MLE。你别只知道开nxt[26]，如果字符集是数字或大小写混合，要记得改数组大小。一个更省空间的办法是用unordered_map存子节点，但会慢。不紧不慢的方案是直接用固定数组，同时预估节点总数上限。比如最多n个串，每个长度为m，那节点数上限就是n*m左右，别开太小。

3.4 AC自动机：当Trie遇到KMP

AC自动机的本质是“在Trie树上跑KMP”。它解决的是多个模式串同时匹配一个文本串的问题。洛谷里这类题很经典，比如给你一堆模式串，问文本串中哪些模式串出现过、各自出现多少次。

建立AC自动机分三步。第一步，把所有模式串插入Trie。第二步，用BFS构建失配指针。失配指针的含义和KMP的next类似：当前节点匹配失败后，跳到Trie树中另一个节点，使得从根到那个节点形成的字符串是当前已匹配文本串的最长后缀。第三步，把文本串在Trie树上移动，遇到匹配失败就按失配指针跳转，边移动边更新计数。

看起来复杂，但模板写下来其实不长。这里有个容易错的地方：构建fail指针时，如果某个字符的子节点不存在，通常要把它直接指向当前节点的fail指针的对应子节点。这样匹配时就不用判断太多，代码简洁。但如果你保留“不存在就为0”的写法，匹配时就要while循环跳fail。两种都能用，我偏向“补全成完整转移边”，匹配时手感好。

AC自动机的计数有两种：一种只统计哪些模式串出现过，可以在匹配时标记结尾节点；另一种要统计每个模式串出现次数，需要在BFS构建fail之后，把所有节点的贡献沿着fail链反向累加。这个反向累加是很多新手容易漏的，因为不累加的话，一个模式串的满足条件可能会静默丢失。我当时第一次写就是忘了累加，导致答案总是比预期少，后来才明白“文本串经过某节点时，这个节点的所有fail祖先都应被统计”。

4. 实测记录：典型题目从读题到AC的全过程

4.1 一道“模式串匹配”题的思考过程

有一道洛谷上的基础题，输入一个文本串和一个模式串，问模式串在文本串里出现了多少次，模式串可以重叠。我当时看完题目第一反应是“这不一样吗？不重叠计数就直接计数，重叠就要用KMP”。然后我果断写了KMP，以为30分钟AC，结果第一次提交WA了。

问题出在我把“匹配成功后判断下一个位置”写成了j = 0，这是不重叠版本。题目说可以重叠，那就是要让模式串后缀和文本串当前后缀保持部分匹配，匹配成功后应该跳转到ne[j-1]而不是0。我重新改完，AC了。

这道题给我的教训是：以后看到“出现次数”字样，第一件事就是确认题目要求“重叠”还是“不重叠”，再决定j跳哪。这个信息WA一次才知道，太浪费提交次数了。

4.2 一道“多模式串出现次数”题的正确姿势

还有一道题，给了很多短模式串和一个长文本串，问这些模式串在文本中出现的总次数。我第一反应是“KMP只能处理一个模式串，我一个个匹配不就行了”？但算了下数据量：模式串有1e5个，文本串长度1e5，哪怕每个模式串用KMP匹配也要O(n*m)，显然不行。

于是换成AC自动机，把模式串都插入，然后跑一遍文本串。AC自动机匹配过程中，每个节点会标记“当前模式串是否出现过”，但更重要的是BFS后的fail链累加。我搞懂之后终于明白：每个文本串位置可能同时命中多个模式串，这些模式串就是当前节点的fail祖先，不累加就会漏。

这道题AC之后，我对AC自动机的理解才算真正通。后来再遇到“模式串出现次数总和”就不慌了。记住：AC自动机不是只数“被指针直接指向的模式串”，还要数“所有能通过fail指针抵达的模式串”。

4.3 一道“前缀/分词”类题的奇巧解法

还有一类题，给你一个长字符串和一堆短字符串，问长字符串可以由这堆短字符串拼接而成吗。这类题可以暴力DFS，但会超时。我当时灵机一动，想到先用Trie树把所有短字符串存起来，然后在长字符串上DP，每次从当前位置出发，在Trie上顺着字符走，如果能走到某结尾节点，说明存在一个短字符串匹配这个前缀，接着更新DP状态。

这个解法的好处是，不用枚举每种短字符串，而是直接在树上走，复杂度约等于所有可能匹配的总步数，优化了很多。这题让我意识到：字符串算法不是孤立的，Trie + DP的组合在洛谷很常见。不要只会单算法，要能搭起来用。

5. 新手最容易踩的坑，和对应的排查方法

5.1 下标基准混乱，WA到怀疑人生

字符串题最隐蔽的坑就是下标。同一个字符串，char数组是从0开始，但哈希前缀和、KMP的next表、DP数组很多都是1-based。如果你一会儿从0开始取字符，一会儿下标从1开始取哈希值，非常容易错位。

我现在的统一方法是：所有输入字符串先用string存起来，操作时统一用0-based索引；哈希前缀和单独开一个新数组，用1-based前缀长度来存，转换时用s[i-1]。凡是要查询区间，都改成[l, r)半开区间，或者[l, r]闭区间但保证参数用1-based，非常忌讳混用。每次写完代码先做一小段手算样例，验证下标对不对，能省很多提交次数。

5.2 读入空行、空格、换行的血泪教训

洛谷字符串题经常给出多组数据，有些数据行之间有空格，有些行内可能包含空格或者无用的前缀信息。比如读一个整数n之后，接下来有一整行字符串，如果你用cin >> n;然后立刻getline()，会先把换行符读进来，导致第一个字符串是空的。这种经典错误不克服，能让你怀疑到底是算法错还是输入错。

我的处理方式：在cin >> n之后，调用一次getline(cin, consume);把那个换行吃掉，然后再循环读字符串。如果遇到整行带空格的字符串，直接用getline读；如果题目要求“忽略前导空格”，则可以用一个循环清除。Python下则注意input()在包含空行时的行为。

还有一点，洛谷的某些题目会故意在样例里用\r\n换行，这在Windows下可能会让字符串多出一个\r。用C++读如果遇到这个，字符串尾部会多一个字符，匹配时匹配不到。解决方法是读入后跳过\r或者统一用cin（它不管\r），但要注意别手滑把合法字符删了。

5.3 哈希模数跟自然溢出，到底选哪个

关于哈希碰撞，很多新手会问到底是单模数还是自然溢出。我的建议是：如果数据不是故意构造卡哈希的，自然溢出完全够用；但如果你在刷一块难一点的题，比如那种让你判断很多子串相等，然后数据范围很大，可能被卡。这时候用双哈希更稳妥，代价是常数稍大。

双哈希可以用两个不同的unsigned long long自然溢出值，也可以用一个long long质数模数+一个unsigned long long自然溢出。我常用的是：

const int MOD1 = 1e9+7; const int MOD2 = 1e9+9;

然后分别维护两个哈希数组。查询时两个值都相等才判等。写起来稍长，但可靠。

另有个误区：base不能取1，不然所有字符串哈希值都一样，那是自毁。base也不要太靠近模数，否则随机数据下冲突概率也会偏高。131、13331都没问题。

5.4 递归建树爆栈，TLE和RE双杀

很多人在写Trie和AC自动机时，喜欢用递归去遍历或统计。但洛谷有些题给你的字符串很长，节点数很多，递归深度一旦到几万，就会爆系统栈，表现为运行错误甚至莫名超时。

我的建议是：Trie的递归只用于“功能”，比如遍历输出所有单词；而AC自动机的构建和fail链累加尽量不要用递归，而是用BFS队列迭代完成。BFS的写法固定，不容易爆。要是真用到递归，可以把递归深度开到100万，但这不是长久之计，最好改成非递归。

6. 刷题节奏与复盘感悟

6.1 用什么顺序刷，心态能稳一点

如果让我给一条刷题路线，我会这样建议：先刷字符串哈希题，因为它最直观，只要你会算前缀和就能做；再刷KMP题，理解next数组的构造；然后刷Trie，因为它很直观；最后刷AC自动机，因为它把KMP和Trie结合了，往后基本上就是套路题。这个顺序对我很有效，因为每一步都是上一步的延伸，不会一上来就一头雾水。

别一上来就挑战性价比低的难题。很多时候会觉得“AC自动机模板背了也写不对”，那可以先回头补一补KMP fail指针的本质。基础没打牢，后面就是空中楼阁。我刷到第10道题时，之前那些背不下来的模板，基本就自然而然地刻进脑子里了。

6.2 怎么把一道题变成一类题

我强烈建议刷完一道题后，在题解或笔记里写这么几行：

• 这题用了什么算法？
• 这题的难点是在读入、下标、还是算法变式？
• 如果我下次遇到类似题目，第一时间该看哪里？

比如我用完一次AC自动机，就总结出“以后如果题目说多个模式串匹配一个文本串，先建Trie，再BFS求fail，匹配后记得累加fail链”。这样一个总结能覆盖绝大多数多模式匹配题。再比如哈希题，我会总结“判断子串相等优先哈希；判断回文长度可二分加哈希”。这些总结写在纸上，比刷十道新题更有用。

6.3 我对字符串题的最终体会

刷了这么久，最大的感受是字符串题特别考验细节。不是算法不懂，而是下标、读入、边界没了就很难受。所以我现在写代码时会刻意把每次模板的边界都标清楚，并且一遍一遍给ne、h数组打样例。做多了以后，胜率明显高了不少。

至于心态，别太执着于“一次AC”。哪怕像KMP这种经典算法，我也经历过WA了四五次才明白哪里错。每次错误都是经验值，记录坑比骂自己更有用。字符串专题刷得好，对其它题也有帮助，因为你会开始用结构和状态去组织字符序列，而不是傻傻扫一遍。希望这篇“刷题有感”能给正在啃字符串的你一点帮助。