---
title: "剪布花条"
created: 2025-11-28
tags:
  - 算法
---

# 剪布花条

## 题目 [剪花布条](https://www.acwing.com/problem/content/description/4190/)

![[image-3e59594b.png]]

## 思路分析

看原串中有多少个模式串

注意点：

读入判断

现场还原

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

char p[N],s[N];

int ne[N];

int main()

{

    while(cin>>s+1)

    {

        if(s[1] =='#' && s[2] == '\0')

            break;

        int res = 0;

        memset(ne, 0 , sizeof ne);

        cin>>p+1;

        int n = strlen(p+1);

        for(int i = 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;

        }

        int m = strlen(s+1);

        for (int i = 1, j =0 ; i <= m; i ++ )

        {

            while(j && s[i] != p[j+1])

                j = ne[j];

            if(s[i] == p[j+1])

                j++;

            if(j == n)

            {

                res++;

                j = 0;

                //注意这里 j必须从0开始,因为前面的布条被剪掉了

                //y总模板课讲的这个地方要还原现场以便后续操作 现在用到了

                //其实就是为了后续还能匹配 即原串中不止一个模式串 这次匹配完了 还原一下 再看后面还有没有

            }

        }

        cout << res <<endl;

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/串相关模型/KMP/KMP|KMP]] 🏠 [[00-刷题理模型]] ➡️ [[kmp 中 next 数组的周期性质|kmp 中 next 数组的周期性质]]