1 class Solution { 2 public: 3     char *strStr( char *haystack, char *needle ) { 4         int hlen = strlen( haystack ), nlen = strlen( needle ); 5         for( int i = 0; i <= hlen-nlen; ++i ) { 6             int j = 0; 7             for( ; j < nlen; ++j ) { 8                 if( haystack[i+j] != needle[j] ) { break; } 9             }10             if( j == nlen ) { return haystack+i; }11         }12         return 0;13     }14 };

 1 class Solution { 2 public: 3     char *strStr( char *haystack, char *needle ) { 4         int hlen = strlen( haystack ), nlen = strlen( needle ); 5         if( nlen == 0 ) { return haystack; } 6         vector<int> jump; 7         GetJumpTable( needle, nlen, jump ); 8         int i = 0, j = 0; 9         while( i <= hlen-nlen ) {10             if( haystack[i+j] != needle[j] ) {11                 if( j == 0 ) {12                     ++i;13                 } else {14                     i += j-1 - jump[j-1];15                     j = jump[j-1]+1;16                 }17             } else {18                 ++j;19                 if( j == nlen ) { return haystack+i; }20             }21         }22         return 0;23     }24 private:25     void GetJumpTable( const char *needle, int nlen, vector<int> &jump ) {26         jump.resize( nlen, -1 );27         for( int i = 1; i <= nlen; ++i ) {28             int k = i-1;29             while( k != -1 ) {30                 k = jump[k];31                 if( needle[k+1] == needle[i] ) {32                     jump[i] = k+1;33                     break;34                 }35             }36         }37         return;38     }39 };