HDU 2087 剪花布条（KMP，不可重叠重复子串）

时间：2023-03-09 22:01:18
HDU 2087 剪花布条（KMP，不可重叠重复子串）

　　给KMP传的数组一定要从0开始！！

　　显然，我们要先把模式串放到前面，之后主串放后面，中间隔开，这样就可以根据前缀数组的性质来求了。

　　这题和我上一篇博客类似，只不过不可重叠，我看了数据范围不大，所以就开了vis数组存是否走过，之后就可以做到不可重叠了。

　　但这题还有个陷阱，就是说了ascii码内都是颜色，所以就不能用'$'来隔离了，我的操作是inp数组赋一个300，这样就超过128，之后就A了

#include <bits/stdc++.h>

using namespace std;

const int INF=0x3f3f3f3f;

typedef long long ll;

#define PI(A) printf("%d\n",A)

#define SI(N) scanf("%d",&(N))

#define SII(N,M) scanf("%d%d",&(N),&(M))

#define cle(a,val) memset(a,(val),sizeof(a))

#define rep(i,b) for(int i=0;i<(b);i++)

#define Rep(i,a,b) for(int i=(a);i<=(b);i++)

#define reRep(i,a,b) for(int i=(a);i>=(b);i--)

const double EPS= 1e- ;

/*  /////////////////////////     C o d i n g  S p a c e     /////////////////////////  */

const int MAXN= + ;

void kmp_pre(int x[],int m,int Next[])

{

    int i,j;

    j=Next[]=-;

    i=;

    while(i<m)

    {

        while(-!=j&&x[i]!=x[j])j=Next[j];

        Next[++i]=++j;

    }

}

int Next[MAXN],inp[MAXN];

int N,M;

char str1[+],str2[+];

bool vis[MAXN];

bool check(int x,int y)

{

    for (int i=x;i<=y;i++)

    {

        if (vis[i]) return false;

    }

    return true;

}

int main()

{

    while(~scanf("%s",str1))

    {

        N=strlen(str1);

        if (N==&&str1[]=='#') break;

        scanf("%s",str2);

        M=strlen(str2);

        str2[M]='$';//这是错的，不能符赋为$，因为题里说是任何ASCII值都是颜色

        for (int i=; i<=M; i++)

        {

            inp[i]=str2[i];

        }

        for(int i=M+; i<=N+M; i++)

        {

            inp[i]=str1[i-M-];

        }

        inp[M]=;//所以这要赋一个超过ASCII值的数

        kmp_pre(inp,N+M+,Next);

        cle(vis,);

        int ans=;

        for (int i=; i<=N+M+; i++)

            if(Next[i]==M&&check(i-M+,i)&&i-M+>=)

            {

                for (int j=i-M+;j<=i;j++)

                vis[j]=;

                ans++;

            }

        PI(ans);

    }

    return ;

}

相关文章