本來以為會和std::basic_string::find一樣複雜度爛掉
沒想到居然比我手爆kmp快上一點點

然後發現在windows上 無論是cl還是gcc 時間都會爛掉
実家のような安心感

這個故事告訴我們 該手爆kmp時還是要乖乖手爆 不要偷懶

btw std::basic_string::find()就不用說了 用3個compiler編出來都會跑超過10分鐘

因為 strstr 現在主流應該都是實作 Two-way string-matching algorithm - Wikipedia 這個演算法？

gslin: 我看到有人貼了glibc的strstr實作 看起來也是是kmpglibc/sysdeps/x86_64/multiarch/strstr.c at master-be...--
btw 有人寫uva時被std::basic_string::find() gank 改成古時候的std::strstr反而過了Can It Be Faster to Find the Minimum Periodic String...不過那八成是因為uva用的是unix 如果今天是poj他還是得乖乖手爆

在 glibc 的官方 repository 裡面，Making sure you're not a bot! 這邊可以看到說明，三個不同的 case：

Fast strstr algorithm with guaranteed linear-time performance.

Small needles up to size 3 use a dedicated linear search.

Longer needles up to size 256 use a novel modified Horspool algorithm.

Needles larger than 256 characters use the linear-time Two-Way algorithm.