字符串匹配的后缀算法

字符串匹配问题是算法领域的经典问题,C/C++中常用的 strstr函数就是这个问题的定义:

const char* strstr( const char* str, const char* target );
char* strstr( char* str, const char* target );

Finds the first occurrence of the byte string target in the byte string pointed to by str. The terminating null characters are not compared.

在目标字符串 str中寻找是否存在子串 target,字符串 str的长度为\(n\), target的长度为\(m\)。这个问题最为人所熟知的算法应该是KMP(Knuth-Morris-Pratt)算法,其时间复杂度为\(O(n)\),想法非常酷。

但是,Can we do better?

继续阅读:

Strict Aliasing,神坑?

先来看一段代码:

你觉得程序的输出是什么样的呢?

继续阅读: