剪布花条

题目 剪花布条

思路分析

看原串中有多少个模式串

注意点：

读入判断

现场还原

代码实现

#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;

}

同类题型

视频讲解

⬅️ KMP 🏠 00-刷题理模型 ➡️ kmp 中 next 数组的周期性质