1 vector
     
       calPrefix(string &p) { 2     int n = p.size(); 3     vector
      
        q(n + 1); 4     q[1] = 0; 5     int k = 0; 6     for (int i = 1; i < n; i++) { 7         while (k > 0 && p[i] != p[k]) k = q[k]; 8         if (p[i] == p[k]) k++; 9         q[i + 1] = k;10     }11     return q;12 }