1 class Solution {
 2 public:
 3     char *strStr(char *str1, char *str2) {
 4 		int len1 = strlen(str1);
 5 		int len2 = strlen(str2);
 6 		if (len2 > len1)
 7 			return NULL;
 8 		int move[len2];
 9 		genMove(str2, move);
10 
11 		int idx1 = 0;
12 		int idx2 = 0;
13 		while (idx1 < len1 && idx2 < len2){		
14 			if (str1[idx1] != str2[idx2]){
15 			    if (!idx2)
16 					idx1 ++ ;
17 			    else
18 				    idx2  = move[idx2];
19 			}
20 			else{
21 				idx1++;
22 				idx2++;
23 			}
24 		}
25 
26 		if (idx2 == len2)
27 			return str1 + idx1 - len2;
28 		
29 		return NULL;
30     }
31 
32 	void genMove(char* str, int move[])
33 	{
34 		int n = strlen(str);
35 
36 		int idx = 0;
37 		move[0] = 0;
38 		for (int i = 1; i < n; ++ i){
39 		move[i] = idx++;
40 			if (str[i] != str[idx])
41 				idx = 0;			
42 		}      
43 	}
44 };