ACM 二進制字符串匹配：KMP / string::find 統計子串出現次數

題目大意

給定模式串 A（長度 ≤10）和文本串 B（長度 ≤1000），僅含 '0'/'1'。統計 A 在 B 中作為子串出現的次數（可重疊）。

解法一：C++ string::find 循環

#include 
#include 
using namespace std;

int main(){
    int T; cin>>T;
    while(T--){
        string A,B; cin>>A>>B;
        int cnt=0;
        for(size_t pos=0; (pos=B.find(A,pos))!=string::npos; ++pos) ++cnt;
        cout<
find 內部實現通常為高效算法（如 Boyer-Moore），對此數據規模完全足夠。

解法二：KMP 模板（教學用）
vector buildLPS(const string& pat){
    vector lps(pat.size());
    for(int i=1,len=0;i

樣例驗證
輸入:
3
11
1001110110
101
110010010010001
1010
110100010101011

輸出:
3
0
3