1 vector<int> calPrefix(string &p) {
 2     int n = p.size();
 3     vector<int> 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] != s[k]) k = q[k];
 8         if (p[i] == p[k]) k++;
 9         q[i + 1] = k;
10     }
11     return q;
12 }