1 2 3 4 5 6 7 8 9 10 11 12 13 | vector< int > kmpProcess(string s) { vector< int > b(s.size(),0); int j = 0; //下面计算b[i] for ( int i = 1; i < s.size(); i++) { while (j > 0 && s[i] != s[j]) j = b[j - 1]; //当前的widest border不满足要求,那么找到next widest border if (s[i] == s[j]) j++; b[i] = j; } return b; } |
原文:http://www.cnblogs.com/zhxshseu/p/ef2f76d5d840793202ab216e5f4f62a5.html