// KMP算法:构建next数组 vector buildNext(const string& pattern) { int n = pattern.size(); vector next(n, 0); int j = 0; for (int i = 1; i < n; ++i) { while (j > 0 && pattern[i] != pattern[j]) { j = next[j - 1]; } if (pattern[i] == pattern[j]) { j++; } next[i] = j; } return next; } // KMP算法:在文本中查找模式串,返回所有匹配的起始位置 vector kmpSearch(const string& text, const string& pattern) { vector result; int n = text.size(); int m = pattern.size(); if (m == 0) return result; vector next = buildNext(pattern); int j = 0; for (int i = 0; i < n; ++i) { while (j > 0 && text[i] != pattern[j]) { j = next[j - 1]; } if (text[i] == pattern[j]) { j++; } if (j == m) { result.push_back(i - m + 1); j = next[j - 1]; } } return result; }