1 条题解
题解与来源题共享。已有题解默认通过；新增或编辑后需由来源域管理员审核。待审核、驳回题解仅作者和审核管理员可见。来源域：system
-
0
代码：#include
#include #include using namespace std; vector computePrefixFunction(const string& s) { int n = s.length(); vector pi(n, 0); for (int i = 1; i < n; ++i) { int j = pi[i-1]; while (j > 0 && s[i] != s[j]) { j = pi[j-1]; } if (s[i] == s[j]) { j++; } pi[i] = j; } return pi; } int minimalCycleCover(const string& s) { int n = s.length(); vector pi = computePrefixFunction(s); int maxPrefixSuffix = pi.back(); int candidate = n - maxPrefixSuffix; return candidate; } int main() { string s; cin >> s; cout << minimalCycleCover(s) << endl; return 0; }