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 }
原文：http://www.cnblogs.com/ivancjw/p/6389532.html