字符串算法：大海里捞一根“特定的针“，怎么捞得又快又巧？

引子老王的查找关键词烦恼还记得那位一路从查找江湖杀进图的世界、把分治、二分、递归回溯、动态规划、贪心、双指针一身内功都修炼到家的老王吗这天老王的孙子在写作文问他“爷爷春风又绿江南岸’这句诗出自一整篇古文老师让我找出它在第几个字出现可这文章好几千字啊怎么找得快”老王接过文章习惯性地用起了笨办法从文章第1个字开始拿春风又绿江南岸这7个字去比——文章第1个字是明不是春往后挪一个字从第2个字再比第2个字是月也不是春再往后挪一个……好不容易碰到一个春字一对——“春风又明”第4个字就对不上了于是退回去从那个春字的下一个字重头再比……老王比着比着眉头越皱越紧不对劲啊!我这法子太笨了——好不容易比中了好几个字,结果最后一个字对不上,就得全退回去,从头再来!**你看,我明明已经知道’春风又’这几个字对上了,这里头藏着有用的信息啊!可我一对不上就傻乎乎地全退回去、从零再比,把刚才辛辛苦苦得来的线索全扔了**!这不是白费功夫吗?**就不能利用一下’已经比对过’的信息,聪明点、别老退回头吗?老王这一皱眉正皱中了算法世界里一个应用最广、最经典、也最烧脑的领域——字符串算法而它皇冠上那颗最亮的明珠就是字符串匹配在一大段文本里找一个特定的子串。你每天都在用它搜索框里搜关键词、文档里按 CtrlF 查找、浏览器里找网页内容、DNA序列比对……本质全是在一大段字符里找出一小段特定字符出现在哪。而老王的烦恼正是这个领域里笨办法与聪明办法的分水岭笨办法朴素匹配一对不上就全退回去、从头再比把已知线索全扔了聪明办法以KMP为代表充分利用已经比对过的信息绝不退回头一路向前老王搓搓手“利用已比过的信息、绝不退回头……这思路,跟我前几天学的’双指针’那’绝不走回头路’简直一个味儿!可这字符串匹配,到底咋个’不退回头’法?快说说门道!”第一章先看笨办法——朴素匹配笨在哪要懂聪明,得先看清笨。我们把老王的笨办法——朴素匹配——看个透。假设要在文本“ABABABCA”里找子串“ABABC”文本: A B A B A B C A 子串: A B A B C朴素匹配的过程笨在全退回头① 从文本第1位开始对: 文本: A B A B A B C A 子串: A B A B C ✓ ✓ ✓ ✓ ✗ ← 前4个对上!第5位 A≠C,失败! ② 笨办法:子串退回开头,文本指针退回第2位,从头再比: 文本: A B A B A B C A 子串: A B A B C ✗ ← 第2位 B≠A,立马失败! ③ 文本指针再退回第3位,再从头比: 文本: A B A B A B C A 子串: A B A B C ✓ ✓ ✓ ✓ ✓ ← 全对!找到了!在第3位!笨在哪看第②步第①步我们明明已经比对出文本前4位是 ABAB这个宝贵信息可一失败朴素匹配就把文本指针狠狠退回去把这线索全扔了从头再来一遍。这种一失败就全退回头、重复比对正是它慢的根源——文本越长、子串越长退来退去的冤枉功就越多老王点头“果然笨!明明比出’ABAB’了,一失败就全退回去当无事发生,白比了!这跟我对账时’两两都试’的笨劲儿,一个毛病——净走回头路!”第二章聪明办法的灵光——“已经比过的凭啥要退回头”老王的灵光正是所有聪明字符串匹配算法最著名的就是KMP算法的出发点核心灵光当比对到某一位失败时我们其实已经知道失败位置前面那一截文本和子串是完全一样的这是白纸黑字、确凿无疑的信息。与其把它扔掉、退回头重比不如利用它——让子串聪明地往右滑动一段文本指针压根不用退回去我们回到刚才第①步失败的地方看聪明办法怎么做文本: A B A B A B C A 子串: A B A B C ✓ ✓ ✓ ✓ ✗ → 失败前,已知文本和子串都匹配了ABAB这一截! 聪明办法的观察: 子串自己的ABAB里,头上的AB和尾巴上的AB是一样的! → 那失败后,子串不用退回开头,只需滑到—— 让子串开头的AB对齐文本里已匹配的尾巴AB的位置! → 文本指针【纹丝不动】,只把子串向右滑两格: 文本: A B A B A B C A 子串: A B A B C ✓ ✓ ✓ ✓ ✓ ← 接着比就对上了!一步到位!天壤之别朴素匹配傻傻地把文本指针退回去、一格一格重试而聪明办法洞察了子串自己内部的重复规律让子串一下滑到该在的位置文本指针绝不回退省掉了所有退回去重比的冤枉功。老王恍然大悟“妙啊!它看穿了子串’ABAB’里头藏着’AB…AB’的重复花样——一失败,不退文本,只把子串’唰’地往右滑到位,接着比!这’绝不退文本、只滑子串’的劲儿,可比我那’全退回头’高明太多了!”第三章KMP的秘密武器——一张退路表next数组老王较真起来“可子串一失败,到底该往右滑几格?它咋知道滑到哪儿正好?”问到点子上了KMP算法的精髓全在它事先准备好的一张小本本——专业上叫next数组咱们叫它退路表┌────────────────────────────────────────────────┐ │ 退路表(next数组)是干啥的? │ │ │ │ 它事先研究透了【子串自己】—— │ │ 把子串每一个位置上,开头和这之前那截的最长重复 │ │ 都算好、记在表上! │ │ │ │ → 一旦在某位失败,查一下这张表, │ │ 立刻就知道子串该滑到哪、从哪一位接着比! │ │ → 不用思考、不用退文本,查表即得! ⚡ │ └────────────────────────────────────────────────┘关键思路KMP 把功夫下在了开比之前——它先花一点时间仔细研究子串自身的重复结构哪一截开头和哪一截结尾长得一样把每个位置的失败退路都算好、记进退路表。这样真正比对时一旦失败查表一步到位绝不回退文本飞快地一路扫到底看出门道了吗这事先把信息算好、记在表上、用时直接查的劲儿和动态规划那绝不重算、记在小本本上简直一脉相承KMP 就是用一张退路表把重复比对的冤枉功彻底消灭了。老王拍案“原来如此!它开比之前,先把子串自己的’重复花样’摸透、记成一张’退路表’!比对时一失败,查表就知道滑哪儿——这’先做功课、用时查表’的精明,跟动态规划那小本本,真是一个师父教的!”第四章威力揭秘——KMP到底快多少老王最关心这’绝不退回头’到底能快多少我们算笔账。┌────────────────────────────────────────────────┐ │ 在【100万字】的文本里,找一个【100字】的子串: │ │ │ │ 【朴素匹配】一失败就退回头重比: │ │ 最坏情况,每个位置都要重比近100次 │ │ → 约 100万×100 1亿次! │ │ │ │ 【KMP】文本指针绝不回退,一路向前: │ │ 文本扫一遍(100万) 做退路表(100) │ │ → 约 100万次! ⚡ │ │ │ │ → 1亿次 vs 100万次,快了约100倍! │ └────────────────────────────────────────────────┘威力的根源KMP 的精髓就是让文本指针只进不退——从头到尾一路向前扫一遍就够了朴素匹配慢慢在退回头重比KMP 快快在绝不回头。文本有多长它就走多少步干净利落专业上叫O(NM)文本长N子串长M是字符串匹配里梦寐以求的速度。老王倒吸一口凉气“1亿次压到100万次!就靠’文本指针绝不回退、一路向前’这一条!原来’不走回头路’这四个字,值这么多!”第五章字符串算法的大家族——不止匹配老王意犹未尽“字符串算法,就只有’找子串’这一招吗?”当然不止找子串只是最经典的代表。字符串算法是一个枝繁叶茂的大家族我们点几个常见的成员让老王开开眼┌────────────────────────────────────────────────┐ │ 字符串算法大家族(常见成员): │ │ │ │ · 字符串匹配:大文本里找子串(KMP/BM/Sunday…) │ │ → 搜索、CtrlF查找的基石 │ │ │ │ · 多模式匹配:一次性找一大堆关键词(AC自动机) │ │ → 敏感词过滤、关键词高亮 │ │ │ │ · 回文判断:正着读反着读一样吗?(上海自来水…) │ │ → 常用中心扩散或双指针两头夹 │ │ │ │ · 最长公共子串/子序列:两段话有多像?(常用动态规划)│ │ → 文章查重、DNA比对、拼写纠错 │ │ │ │ · 字典树(Trie):像字典一样组织海量单词 │ │ → 输入法联想、搜索框自动补全 │ └────────────────────────────────────────────────┘看出门道了吗字符串算法的精彩在于它把前面学的各路内功都用上了——回文判断用双指针两头夹文章查重、求最长公共子串用动态规划字典树是棵特殊的树……字符串正是检验你那一身算法内功的综合考场老王赞叹“好家伙!敏感词过滤、查重、输入法联想……原来天天用的这些,背后都是字符串算法!而且双指针、动态规划、树全都用上了——这真是个’内功大检阅’啊!”第六章终极总结——字符串算法到底妙在哪老王把字符串算法的智慧浓缩成一张表┌────────────────┬──────────────────────────────────┐ │ 字符串算法 │ 说明 │ ├────────────────┼──────────────────────────────────┤ │ 最经典问题 │ 字符串匹配:大文本里找子串 │ │ 笨办法 │ 朴素匹配:一失败就全退回头重比 │ │ 笨在哪 │ 扔掉已比对的线索,重复比对,慢 │ │ 聪明办法(KMP) │ 利用已比信息,文本指针绝不回退 │ │ 秘密武器 │ 退路表(next):事先摸透子串重复 │ │ 思想血缘 │ 像动态规划:先算好记表,绝不重复 │ │ 威力 │ O(NM):文本扫一遍,快百倍! ⚡ │ │ 大家族 │ 匹配/回文/查重/字典树…内功大检阅 │ │ 一句话 │ 利用已知线索,绝不退回头,一路扫到底│ └────────────────┴──────────────────────────────────┘老王摸着这张表悟出了字符串算法的题眼我总算把这’捞针’的本事看透了——笨办法的笨,在于一遇挫折就全盘退回、从头再来**,把辛苦得来的线索全当废纸扔了;聪明办法的妙,恰恰在于死死攥住’已经比对过’的每一分线索,绝不退回头,让那只’捞针的手’,从头到尾只往前、不回缩!**它的秘诀,还是那个’先做足功课’——开比之前,先把要找的东西自己的’门道’摸了个透,记成一张’退路表’;真碰了壁,查表一步到位,绝不慌乱重来!原来,真正的高手捞针,不是大海里瞎捞、碰壁就从头来过,而是攥紧每一分线索、做足功课、绝不走回头路——把’踏破铁鞋’的蛮力,化成了’一路向前’的从容!尾声一手绝不退回头的捞针本领亦是人生的智慧老王这场对字符串算法的钻研从查找关键词的笨办法出发看清了朴素匹配一失败就全退回头的笨拙领略了KMP利用已知线索、绝不退回头、先做退路表的精妙更见识了字符串这个内功大检阅的枝繁叶茂——终于把这门天天都在用、却又最烧脑的本领握进了手心。但当我们合上书会发现这一手绝不退回头的捞针本领背后竟也舒展着几分耐人寻味的人生哲理。第一碰了壁别急着全盘退回、从头再来——你走过的每一步都留下了线索。字符串算法最深的智慧是它对全盘退回的拒绝——朴素匹配一遇挫折就把文本指针狠狠退回、把辛苦比对的线索当废纸扔掉而聪明的KMP死死攥住已经比对过的每一分信息绝不退回头。这何尝不是一记对人生的点拨我们遭遇失败、碰了壁时最容易陷入的恰恰是那种全盘否定、推倒重来的沮丧——一次创业失败就觉得过去几年全白费了一段努力没结果就想把一切清零、从头再来。可KMP告诉我们:你走过的每一步、踩过的每一个坑、积累的每一分经验,都不是’白费’——它们正是你下一步’不必再退回头’的宝贵线索!真正的智者碰壁后不是抹掉一切重来而是带着’已经走过的收获’,从当下这一步,聪明地接着往前。失败不可怕可怕的是把失败里攒下的线索,也一并扔掉、回到原点。第二“先做足功课”远胜过临场碰壁了再慌乱。KMP之所以快关键在它把功夫下在了开比之前——先静下心把要找的东西摸了个透做好那张退路表于是真正比对时碰了壁也能查表一步到位、从容不乱。这给我们一个朴素而深刻的启示真正的高手从不打无准备之仗。那些临场看似反应神速、遇事不慌的人背后往往是事先做足了功课、把各种退路都预想周全的结果。反观许多人,做事不肯花前期’摸透门道’的功夫,一头扎进去,一碰壁就手忙脚乱、推倒重来——看似省了准备的功夫,实则赔上了无数次慌乱重来的代价。磨刀不误砍柴工——肯在动手前下足’摸透门道、备好退路’的笨功夫,才换得来临场时’碰壁不慌、一路向前’的真从容。第三一身本事的价值要在综合考场上才真正显现。字符串算法这个大家族最迷人的是它把双指针、动态规划、树……前面学的各路内功,全都调动起来、融会贯通——回文用双指针、查重用动态规划、联想用字典树。单独一招或许平平,合在一起,却能解决一个个鲜活的真问题。这是一种了不起的集大成智慧。生活与工作中那些真正能解决复杂难题的人,往往不是只精一门绝技的’专才’,而是能把多种知识、技能、经验融会贯通、随手调用的’通才’。学过的东西别让它们各自孤立、积灰生锈——真正的本事,是在面对一个综合的真难题时,能把它们像拼积木一样调动起来、组合发力。知识唯有融会贯通、学以致用才从纸上的招式变成你手中真能成事的本领。下次当你在搜索框里敲下关键词、瞬间得到结果或是遭遇一次挫折、忍不住想全盘推倒重来时请记得这门捞针本领的智慧——像KMP那样碰了壁别急着全盘退回攥紧你已经走过的每一分线索从当下聪明地接着往前像它那样凡事先做足功课、备好退路方能临场不慌、一路从容更像那个内功大检阅的字符串家族那样把一身所学融会贯通在真难题的考场上,组合发力。于是再浩瀚如海的茫茫文本再棘手难缠的现实难题也终将在你绝不退回头、做足功课、融会贯通的从容里被你又快又巧地——捞出那根针。“字符串算法”就是这门关于碰壁别全盘退回、先做足功课、融会贯通学以致用的、朴素而深刻的智慧。它告诉我们碰了壁别急着全盘退回你走过的每一步都留下了线索先做足功课远胜过临场慌乱一身本事的价值要在综合考场上才真正显现。它像一句朴素的箴言提醒着我们——碰了壁别把走过的路一并抹掉、推倒重来攥紧每一分线索从当下聪明地接着往前凡事先下足摸透门道、备好退路的功夫方换得临场碰壁不慌、一路向前的从容别让学过的本事各自积灰把它们融会贯通、组合发力才是真能成事的本领——一个懂得不全盘退回、先做足功课、融会贯通的人才能像那只绝不退回头的捞针之手纵使面对浩瀚如海、望不到头的茫茫文本也总能攥紧线索做足功课绝不回头一路向前又快又巧地从万千字符里稳稳捞出那根特定的针。这就是藏在字符串算法背后那一手绝不退回头最深、也最美的浪漫。