【ACWing】4187. 剪花布条

题目地址：

https://www.acwing.com/problem/content/4190/

一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？

输入格式：
输入数据为多组数据，读取到#字符时结束。每组数据仅有一行，为由空格分开的花布条和小饰条。花布条和小饰条都是用可见ASCII字符表示的，不会超过1000 10001000个字符。

注意：这个#应为单个字符。若某字符串开头有#，不意味着读入结束！

输出格式：
对于每组数据，输出一行一个整数，表示能从花纹布中剪出的最多小饰条个数。

数据范围：
对于全部数据，字符串长度≤ 1000 ≤1000≤1000。

KMP。代码如下：

#include<iostream>#include<vector>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string s,p;staticautobuild_ne=[](string&p){intn=p.size()-1;vector<int>ne(p.size());for(inti=2,j=0;i<=n;i++){while(j&&p[i]!=p[j+1])j=ne[j];if(p[i]==p[j+1])j++;ne[i]=j;}returnne;};while(cin>>s){if(s=="#")break;cin>>p;intn=s.size(),m=p.size();s=" "+s;p=" "+p;autone=build_ne(p);intres=0;for(inti=1,j=0;i<=n;i++){while(j&&s[i]!=p[j+1])j=ne[j];if(s[i]==p[j+1])j++;if(j==m){res++;j=0;}}printf("%d\n",res);}}

每个数据时间复杂度O ( l s + l p ) O(l_s+l_p)O(ls​+lp​)，空间O ( l p ) O(l_p)O(lp​)。