题意：

封装了一个可KMP匹配的类结构，比较高效。

代码：

// HihoCoder - 1015 #include <iostream> #include <string> #include <vector> class ModelString { private: std::string s; std::vector<int> dp; // dp[i]表示：s[0]~s[dp[i]] 和 s[i-dp[i]]~s[i] 相同 len = dp[i]+1 public: ModelString(); ModelString(std::string s); std::vector<int> kmp(std::string t); }; ModelString::ModelString() { s.clear(); dp.clear(); } ModelString::ModelString(std::string s) { this->s = s; dp.push_back(-1); // init dp for (int i = 1; i < s.length(); i++) { if (s[i] == s[dp[i - 1] + 1]) { dp.push_back(dp[i - 1] + 1); } else { int now = i - 1; while (now != -1 && s[i] != s[dp[now] + 1]) { now = dp[now]; } if (now == -1) { dp.push_back(-1); } else { dp.push_back(dp[now] + 1); } } } } std::vector<int> ModelString::kmp(std::string t) { std::vector<int> ret; int i = 0, j = 0; while (i < s.length()) { if (s[i] != t[j]) { if (j != 0) { j = dp[j - 1] + 1; } else { i++; } } else { i++, j++; if (j == t.length()) { ret.push_back(i - t.length()); j = dp[j - 1] + 1; } } } return ret; } int main() { int T; std::cin >> T; while (T--) { std::string s, t; std::cin >> t >> s; ModelString ans = ModelString(s); std::cout << ans.kmp(t).size() << std::endl; } }