剪花布条

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 974 字

KMP不重叠匹配计数，遇#结束

一本通
例

正文

// 原题：https://oj.yecheng.tv/p/T1465
// 题意：多组数据，每行两个可见 ASCII 串（花布条、小饰条），读到单独一个 "#" 行结束，输出最多能剪出几块互不相交的小饰条。
// 思路：对小饰条求前缀函数后在花布条上跑 KMP，每凑满一次匹配计数加一并把 j 归零，实现不重叠计数。
// 复杂度：O(|花布条|+|小饰条|) 时间 / O(|小饰条|) 空间
// 易错点：本题是不重叠计数，匹配后 j 要归零而非回退 next；结束标志是整行只有一个 #，以 # 开头的更长串不能终止。
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string a,b;
    while(cin>>a){
        if(a=="#") break;
        if(!(cin>>b)) break;
        int m=(int)b.size();
        vector<int> nxt(m+1,0);
        for(int i=1;i<m;i++){
            int j=nxt[i];
            while(j>0&&b[i]!=b[j]) j=nxt[j];
            if(b[i]==b[j]) j++;
            nxt[i+1]=j;
        }
        int ans=0,j=0;
        for(int i=0;i<(int)a.size();i++){
            while(j>0&&a[i]!=b[j]) j=nxt[j];
            if(a[i]==b[j]) j++;
            if(j==m){
                ans++;
                j=0;
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

剪花布条

正文

一本通·提高篇的其它内容