1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Dec 17, 2014
4+ Problem: Implement strStr()
5+ Difficulty: Easy
6+ Source: https://oj.leetcode.com/problems/implement-strstr/
7+ Notes:
8+ Implement strStr().
9+ Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
10+
11+ Solution: 1. Check in the haystack one by one. If not equal to needle, reset the pointer.(TLE)
12+ 2. Classice KMP solution.
13+ 3. Simplified RK Soluiton. Thanks for [wenyuanhust, wenyuanhust@gmail.com]
14+ */
15+
16+ public class Solution {
17+ public int strStr_1 (String haystack ,String needle ) {
18+ int sLen =haystack .length (),tLen =needle .length ();
19+ if (tLen ==0 )return 0 ;
20+ if (haystack ==null ||needle ==null ||sLen ==0 )return -1 ;
21+ int i =0 ,j =0 ;
22+ while (i <sLen ) {
23+ for (j =0 ;j <tLen && (i +j ) <sLen &&haystack .charAt (i +j ) ==needle .charAt (j ); ++j );
24+ if (j ==tLen )return i ;
25+ ++i ;
26+ }
27+ return (int )-1 ;
28+ }
29+ void getNext (String T ,int []next ){
30+ int i =0 ,j =-1 ;
31+ next [0 ]=-1 ;
32+ int n =next .length ;
33+ while (i <n -1 ){
34+ while (j >-1 &&T .charAt (j )!=T .charAt (i ))j =next [j ];
35+ ++i ; ++j ;
36+ if (i <n -1 &&j <n -1 &&T .charAt (j )==T .charAt (i ))next [i ]=next [j ];
37+ else next [i ]=j ;
38+ }
39+ }
40+ public int strStr_2 (String haystack ,String needle ) {
41+ int sLen =haystack .length (),tLen =needle .length ();
42+ if (tLen ==0 )return 0 ;
43+ if (haystack ==null ||needle ==null ||sLen ==0 )return -1 ;
44+ int []next =new int [tLen +1 ];
45+ getNext (needle ,next );
46+ int i =0 ,j =0 ;
47+ while (i <sLen ) {
48+ while (j > -1 &&needle .charAt (j ) !=haystack .charAt (i ))j =next [j ];
49+ ++i ; ++j ;
50+ if (j ==tLen )return i -j ;
51+ }
52+ return -1 ;
53+ }
54+ public int strStr_3 (String haystack ,String needle ) {
55+ int sLen =haystack .length (),tLen =needle .length ();
56+ if (tLen ==0 )return 0 ;
57+ if (haystack ==null ||needle ==null ||sLen ==0 ||sLen <tLen )return -1 ;
58+ long fh =0 ,fn =0 ;
59+ int head =0 ,tail =tLen -1 ;
60+ for (int i =0 ;i <tLen ; ++i ) {
61+ fh +=haystack .charAt (i );
62+ fn +=needle .charAt (i );
63+ }
64+ while (tail <sLen ) {
65+ if (fn ==fh ) {
66+ int i =0 ;
67+ while (i <tLen &&needle .charAt (i ) ==haystack .charAt (i +head )){
68+ ++i ;
69+ }
70+ if (i ==tLen )return head ;
71+ }
72+ if (tail ==sLen -1 )return -1 ;
73+ fh -=haystack .charAt (head ++);
74+ fh +=haystack .charAt (++tail );
75+ }
76+ return -1 ;
77+ }
78+ }
