字符串匹配问题是算法领域的经典问题，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？
先来看一段代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <cstdio> void exchange(int input, int* output) { short* pi = (short*)&input; short* po = (short*)output; po[1] = pi[0]; po[0] = pi[1]; } int main() { int input = 0xffff0000; printf("input : 0x%08x\n", input); int output = 0xababbaba; exchange(input, &output); printf("output : 0x%08x\n", output); return 0; } |
你觉得程序的输出是什么样的呢？
