28. 实现 strStr()

 1 //KMP算法
 2 class Solution 
 3 {
 4 public:
 5     //求next数组
 6     vector<int> pre(string& str2)
 7     {
 8         if(str2.size() == 1) return {-1};
 9         vector<int> next(str2.size());
10         next[0] = -1;
11         next[1] = 0;
12         int i = 2;
13         int cn = 0;//cn属于可以跳到的位置
14         while(i < str2.size())
15         {
16             if(str2[i - 1] == str2[cn]) next[i++] = ++cn;
17             else
18             {
19                 if(cn > 0) cn = next[cn];
20                 else next[i++] = 0;
21             }
22         }
23         return next;
24     }
25 
26     //str1长串、str2模式串
27     int strStr(string str1, string str2) 
28     {
29         if(str1.size() < str2.size()) return -1;
30         if(str2.empty()) return 0;
31         int i1 = 0;
32         int i2 = 0;
33         vector<int> next = pre(str2);
34 
35         while(i1 < str1.size() && i2 < str2.size())
36         {
37             if(str1[i1] == str2[i2])
38             {
39                 i1++,i2++;
40             }
41             else if(next[i2] == -1) i1++;
42             else i2 = next[i2];
43         }
44         return i2 == str2.size() ? i1 - i2 : -1;
45     }
46 };