[LeetCode] 28. Find the Index of the First Occurrence in a String about leetcode HOT 1 OPEN

class Solution {
public:
    int strStr(string s, string p) {
      if(p.empty()) return 0;
      vector<int> next_char_to_be_matched(p.size(), 0);
      for(int i = 1, k= 0; i < p.size(); ++i){
        while(k && p[i] != p[k]) k = next_char_to_be_matched[k-1];   
        if(p[i] == p[k] ) ++k;
        next_char_to_be_matched[i] = k;
      }
      for(int i = 0, k= 0; i < s.size(); ++i){
        while(k && s[i] != p[k]) k = next_char_to_be_matched[k-1];   
        if(s[i] == p[k] ) ++k;
        if(k == p.size()) return i+1-k;
      }
      return -1;
    }
};