原题来自：HDU 2087

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

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

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

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

abcde a3
aaaaaa aa
#

0
3

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

题目分析

本题是一道经典的字符串匹配问题，核心场景为“模式串在主串中的不重叠出现次数”。 给定一个主串（花布条S1​）和一个模式串（小饰条S2​），要求计算在主串中最多能完整剪出多少个模式串。题目特别强调了“剪出”这一物理动作，这意味着匹配过的字符不能再参与后续的匹配（即不可重叠）。 数据范围：字符串长度≤1000，包含多组测试数据，以单字符#结束。

思考过程

拿到这道题，最直接的反应是字符串匹配。暴力解法的时间复杂度为O(N×M)，对于1000的数据规模，在较优的常数下其实是可以过的。但作为算法训练，显然更期望使用线性时间复杂度的进阶算法。

由此引出两个方向：

1. 基于状态转移的KMP算法：KMP原本用于求解所有匹配位置（允许重叠）。如何将其改造为“不重叠”匹配？关键在于匹配成功后的状态回退机制。

2. 基于数值映射的字符串哈希：将字符串转换为P进制数，通过前缀和思想在O(1)时间内比较任意子串。对于不可重叠的要求，只需要在匹配成功后控制滑动窗口的指针大幅跳跃即可。

解题思路与算法设计

解法一：KMP算法（0-base现代模板）

算法设计： 标准的KMP在匹配成功后，为了寻找下一个可能的重叠匹配，通常会执行j=nxt[m-1]（假设为0-base下标）来回退。 但本题是“剪布条”，一旦匹配成功，这部分主串就被物理切除了。因此，当 j==m 触发时，计数器cnt++，随后直接强制状态清零j=0。这相当于让模式串重新从头开始，与主串剩下的部分继续进行全新的匹配。

解法二：字符串哈希（1-base前缀哈希）

算法设计： 利用自然溢出（unsigned long long）和Base 131进行哈希预处理。 为了避免处理极度繁琐的负数下标问题，哈希数组采取1-base存储。即ans1[i]表示主串前i个字符的哈希值。 对于任意区间 [L,R] 的哈希值，利用公式Hash(L,R)=ans[R]-ans[L-1]*p[R-L+1]在 O(1)时间内求出。 匹配时，维护一个指向主串的指针i：

• 若以i为起点，长度为len2的子串哈希值等于模式串的哈希值，则匹配成功。计数器 cnt++，同时指针直接跳过已匹配区间，执行i=i+len2。

• 若匹配失败，则指针右移一位，执行i++。

易错总结

1. 多组数据读入的阻塞陷阱 题目规定以单个#结束。很多同学习惯写 while(cin>>s1>>s2)。当最后一行只有一个#时，s1会读入#，而程序会阻塞等待s2的输入，虽然信息学奥赛一本题可以通过，但容易导致评测机卡死报超时。 正解： 先读取s1探路，判断若为#则立刻break，确认安全后再读取s2。

2. KMP的Next 数组赋值位置 在求next数组时，nxt[i]记录的是以索引i结尾的子串的最长公共前后缀长度。必须写成nxt[i]=j，切忌笔误写成nxt[j]=j。

3. 哈希匹配的越界问题 在哈希解法的while循环中，如果直接写while(i<=len1)，当主串剩余长度小于模式串时，依然会去截取长度为len2的子串计算哈希，这会导致gethash访问到未定义或越界的内存（如 ans1[1000+500]）。 正解： 循环条件必须严格限制为 while(i+len2-1<=len1)。

时空复杂度分析

• KMP解法：

  • 时间复杂度：求next数组耗时O(M)，主串匹配耗时O(N)。单组测试数据时间复杂度为O(N+M)。

  • 空间复杂度：需要一个长度为M的nxt数组，空间复杂度O(M)。

• 哈希解法：

  • 时间复杂度：预处理前缀哈希数组耗时O(N+M)，滑动窗口扫描匹配耗时O(N)。单组测试数据时间复杂度为O(N+M)。

  • 空间复杂度：需要存储两个长度为N级别的前缀哈希数组，空间复杂度O(N+M)。

---

完整代码

方法一：KMP 算法（0-base）

//第一种做法 KMP
#include <iostream>
#include <cstring>//对应memset
using namespace std;
string s1,s2;//s1是长花布条（主串），s2是小饰条（模式串）
int nxt[1010];//nxt[i]表示从下标0到i的子串中，最长相等“真前后缀”的长度
int cnt;//能从花纹布中剪出的最多小饰条个数

//预处理s2 求出next数组（0-base）
void pre(){
    int m=s2.size();
    int j=0;//j代表当前已经成功匹配的“前缀长度”
    //i从1开始往后扫描 因为只有一个字符(i=0)时，没有“真”前后缀，nxt[0]必然是0。
    for(int i=1;i<m;i++){
        //如果新来的字符s2[i]和期待的字符s2[j]不一样
        //说明这条路走不通了。我们要去查“最后一个成功匹配的字符”，看看能退到哪
        //最后一个成功匹配的字符下标是j-1 所以查nxt[j-1]
        while(j>0&&s2[i]!=s2[j]) j=nxt[j-1];
        //如果对上了，匹配成功的长度j就加1
        if(s2[i]==s2[j]) j++;
        //把算出来的最长相等前后缀长度j，存入nxt[i]
        nxt[i]=j;
    }
}

//主串s1匹配模式串s2
//拿着s2的nxt档案，去s1里面一路向右找
void kmp(){
    int j=0;//此时j代表在主串s1中 当前已经匹配成功了几个s2的字符
    //i遍历主串s1的每一个字符 绝不回头
    for(int i=0;i<(int)s1.size();i++){
        //如果发现主串字符s1[i]和模式串期待的s2[j]不一样
        //查询nxt 看看上一个成功字符(j-1)能让我们退回哪个备用位置
        while(j>0&&s1[i]!=s2[j]) j=nxt[j-1];
        //对上了 匹配长度j增加1
        if(s1[i]==s2[j]) j++;
        //当匹配成功的长度j 正好等于模式串的总长度时
        //即在主串里完整地找到了一块小饰条
        if(j==(int)s2.size()){
            cnt++;
            //题目要求剪下这块布 意味着后面绝不能和这部分发生重叠
            //所以我们直接让j=0
            //强迫模式串在主串的下一个字符处 从头开始进行一次全新的匹配
            j=0;
        }
    }
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin>>s1){
        //读取到#字符时结束
        if(s1.size()==1&&s1[0]=='#') break;
        cin>>s2;
        cnt=0;//每轮开始前要初始化可以剪下块数为0
        //每一轮开始要初始化next数组为0
        memset(nxt,0,sizeof(nxt));
        //现在为0-base写法 因为字符串是从s[0]开始存储的
        //我们课上学习的是1-base写法 如果想1-base去写 
        //只需要给s1 s2前面加个空格即可 最后长度-1 这里不做演示了
        //先预处理next数组 
        pre();
        //然后kmp找最多可以剪下多少块
        kmp(); 
        cout<<cnt<<"\n";
    }
    return 0;
}

方法二：字符串哈希算法

//哈希做法
#include <iostream>
using namespace std;
typedef unsigned long long ull;
string s1,s2;
ull ans1[1010];
ull ans2[1010];
ull p[1010];//p[i]为131的i次方

//返回s1字符串闭区间[l,r]的哈希值
ull gethash1(int l,int r){
    if(l>r) return 0;
    return ans1[r]-ans1[l-1]*p[r-l+1];
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    //预处理p数组
    p[0]=1;
    for(int i=1;i<=1005;i++) p[i]=p[i-1]*131;
    while(cin>>s1){
        if(s1.size()==1&&s1[0]=='#') break;
        cin>>s2;
        //初始化可以剪出的个数为0
        int cnt=0;
        int len1=s1.size();//字符串s1的长度
        int len2=s2.size();//字符串s2的长度
        //1-base去存s1的前缀哈希值
        for(int i=1;i<=len1;i++) ans1[i]=ans1[i-1]*131+s1[i-1];
        //1-base去存s2的前缀哈希值
        for(int i=1;i<=len2;i++) ans2[i]=ans2[i-1]*131+s2[i-1];
        //先计算出s2整体的哈希值
        ull sum2=ans2[len2];
        //接下来去s1中匹配
        int i=1;//从起点开始遍历s1（因为是1—base存储的哈希值）
        while(i+len2-1<=len1){//必须确保从i开始剩下的长度足够剪出一块小饰条
            //获取s1从i到i+len2-1的哈希值(即与s2长度相等的一段的哈希值)
            ull sum1=gethash1(i,i+len2-1);
            //如果sum1等于sum2 代表匹配成功一对
            if(sum1==sum2){
                cnt++;
                //下一次遍历从i+len2开始
                i=i+len2;
            }
            //如果sum1不等于sum2 i往后移动一格 继续检查
            else i++;
        }
        cout<<cnt<<"\n";
    }
    return 0;
}