這就是算法！ 奶茶店追兇記：如何用KMP算法在人群中鎖定嫌疑人？

炎熱的暑假 奶茶店門口早已排起了長龍 計算機專業的大學生張三 在這兼職打工 您好 一滴油奶茶店 有什麼可以幫您 你好 我是警察 請你先保持冷靜 不要做出異常動作 請問您是對我們的訂單 有什麼問題嗎 我們接到舉報 在你店門前排隊的人群中 有一名疑似攜帶危險品的男子 警力正在趕來 但情況緊急 需要你配合確認嫌疑人 張三心頭未緊 冷汗頓時冒了出來 他下意識看向門外的長龍 請問您點的奶茶是哪一款 需要加什麼小料 嫌疑人是身穿灰色T恤 中等身材男子 無明顯特徵 但目擊者提供了一個關鍵信息 附近人的衣服顏色是 白黑白白黑白灰 由於目擊者就在嫌疑人身後 爲了不打草驚蟄 我們只能尋求你的幫助 請你注意嫌疑人的動向 有異常隨時向我們報告 我馬上給您處理 您記得給個好評啊 掛個電話 張三的心臟狂跳 店前的隊伍少說也有二三十個人 大多數人都是穿的黑白灰 要儘快從中找出 嫌疑人所在的序列位置 從長串裏找紫串 這不就是字不串匹配問題嗎 數據結構課上講過實現的算法 店前的隊伍就是主串 嫌疑人所在的序列就是紫串 要從長串中找到紫串 就得先從頭遍歷主串 假設當前第二個字符是紫串的開頭 然後和紫串逐個匹配 如果某個字符匹配不上 再假設主串的下一個 第二加一個字符是紫串的開頭 然後和紫串逐個匹配 直到紫串全部匹配上 就找到了他在主串中的位置 張三決定一邊在腦子裏便利紫串 一邊用眼睛便利主串 他集中生智 一把抓緊桌上的二維碼牌子 先生您好 美女您好 掃碼領券 下單歷檢三塊 第一個人是白色 假設他是紫串的開頭 後面是黑色白色 連續三個顏色都匹配上了 張三緊張起來 再看後面的人 黑色不匹配 按照常規的算法 應該回去到第二位顧客身邊 再從頭匹配紫串 要是能只便利一次主串就好了 對啊 我爲什麼不用KMP算法 充分利用已知的主串信息 找到下一個假設紫串的開頭 從而減少比較的燙數 紫串除了第四位沒匹配上 前三位與主串顏色相同 紫串第三位和開頭對上了 那就可以假設主串的第三位 是紫串的開頭 不用從頭看 直接從紫串的第二位 開始接着覈對就行 他繼續讓下一個人掃碼 這人穿着黑色T恤 正好和紫串第二位的黑對上 緊接着是兩個白色黑色白色 連續六個顏色都對上了 張三心臟提到了嗓子眼 重着膽子看向後一個人 一個白色連衣裙女生 不是身穿灰色的嫌疑人 前三位後三位都是白黑白 局勢直接把開頭的白黑白 平移過來 繼續比對 白色連衣裙女生 與紫串第四位匹配成功 他繼續讓下一個人掃碼 這人身穿黑色T恤 正好和紫串第五位的黑對上 緊接着是白色和紫串第六位的白匹配 張三心裏一陣緊張 看向在後面的人 等他看到下一個人穿着灰色T恤時 張三心裏咯噔一下 完整的序列都匹配上了 灰色男子神情緊張 迴避視線 甚至沒有掃張三舉着的二維碼 張三趕緊移開目光 繼續往前推銷 餘光卻死死鎖定目標 沒想到課堂上學的KMP算法 居然在現實中就了場大局 他心中感慨萬千 原來算法真的是可以救命的