Poj 3167 Cow Patterns Hdu 4749 Parade Show (KMP大小关系相同匹配+树状数组)

青旅半醒 2022-08-23 14:50 138阅读 0赞

两道题差不多，区别在于匹配时是否允许重叠

自己写的时候细节没处理好，无限WA。。。。

KMP和exKMP先练到这里，接下来计划研究下被虐了一遍又一遍的后缀数组。。。

昨天再战cet6，这回写作和翻译题简直感人。。。希望这回能过吧。

坑爹的考试周又要开始了，希望做题的时间能够得到保证。

参考了 [poj 3167 - 1292765944的专栏 - 博客频道 - CSDN.NET][poj 3167 - 1292765944_ - _ - CSDN.NET]

两个串的排名串相等当且仅当这两个串的每个位置上的元素前面等于它的元素个数和小于它的元素个数都相等。

用树状数组维护这个性质

**Poj 3167 Cow Patterns**

题意：给定一个模式串，如果在主串中存在这样一个子串：子串长度与模式串长度相同，且子串中各个数字的大、小、同关系和模式串中的大、小、同关系是一样的，就称该子串满足条件。比如说模式串：1，4，4，2，3，1 而主串：5,6,2,10,10,7,3,2,9；那么主串第三位开始的2,10,10,7,3,2就是满足条件的。统计有多少子串满足上述条件，输出个数及起始位置。

注意：树状数组从1开始

#include <cstdio>
    #include <cstring>
    
    const int N=25005;
    
    int ss[4*N],tt[N];
    int bit[30];            //树状数组中的元素  
    int m1[N],m2[N];  //(匹配串中)m1表示小于,m2表示小于等于  
    int n,k,s;
    int next[N];
    int ans[4*N],cnt;
    
    #define lowbit(x) ((x)&(-(x)))
    
    int Sum (int k)  
    {  
        int sum=0;  
        while (k>0)  
        {  
            sum+=bit[k];  
            k-=lowbit(k);  
        }  
        return sum;  
    }
    
    void Update (int k,int val)  
    {  
        while (k<=s)
        {
            bit[k]+=val;
            k+=lowbit(k);
        }
    }
    
    void getnext ()
    {  
    	int i=1,j=0,kk;
    	next[1]=0;
    	while (i<=k)
    		if (j==0 || (Sum(tt[i]-1)==m1[j] && Sum(tt[i])==m2[j]))
    		{//符合趋势要求
    			i++,j++;
    			next[i]=j;
    			if (i==k+1) return ;   //避免树状数组访问0
    			Update(tt[i],1);
    		}
    		else
    		{
    			for (kk=i-j+1;kk<=i-next[j];kk++)   //这里对next[j]之前的tt[i]都要消除  
    				Update(tt[kk],-1);
    			j=next[j];
    		}
    }
      
    int kmp ()
    {   //这里对待匹配串用树状数组记录
    	int i=1,j=1,kk;  
    	Update(ss[1],1);  
    	while (i<=n)
    	{
    		if (j==0 ||(Sum(ss[i]-1)==m1[j] && Sum(ss[i])==m2[j]))
    		{
    			++i,++j;
    			if (i<=n) Update(ss[i],1);
    		}  
    		else
    		{
    			for (kk=i-j+1;kk<=i-next[j];kk++)  
    				Update(ss[kk],-1);
    			j=next[j];  
    		}  
            if (j>k) //找到了匹配
    		{
    			for (kk=i-j+1;kk<=i-next[j];kk++)
    				Update(ss[kk],-1);
    			cnt++;
    			ans[cnt]=i-1; //记录结尾位置
    			j=next[j];
    		}
    	}
    	return cnt;
    }
    
    int main ()
    {
    	int i;
    	scanf("%d%d%d",&n,&k,&s);
    	for (i=1;i<=n;i++)
    		scanf("%d",&ss[i]);
    	
    	cnt=0;
    	memset(bit,0,sizeof(bit));
    	memset(m1,0,sizeof(m1));
    	memset(m2,0,sizeof(m2));
    	
    	for (i=1;i<=k;i++)
    	{
    		scanf("%d",&tt[i]);
    		Update(tt[i],1);
    		m1[i]=Sum(tt[i]-1);
    		m2[i]=Sum(tt[i]);
    	}
    	
    	memset(bit,0,sizeof(bit));
    	getnext();
    	
    	memset(bit,0,sizeof(bit));
    	printf("%d\n",kmp());
    	for (i=1;i<=cnt;i++)
    		printf("%d\n",ans[i]+1-k); //由结尾位置输出起始位置
    	return 0;
    }

**Hdu 4749 Parade Show**

2013南京网络赛中的一题，当时用dp搞了半天没出结果……

题意基本相同，但是子串匹配时不能重叠，应该可以KMP时直接处理的，但我没想出来，不得已最后再扫一遍去除重叠的部分。

注意本题是多case，所以记得清空所有的数组

这里有一份暴力的代码：http://vjudge.net/problem/viewSource.action?id=1601050

#include <cstdio>
    #include <cstring>
    
    const int N=100005;
    
    int ss[N],tt[N];
    int bit[30];            //树状数组中的元素
    int m1[N],m2[N];  //（匹配串中）m1表示小于，m2表示小于等于
    int n,k,s;
    int next[N];
    int ans[N],cnt;
    
    #define lowbit(x) ((x)&(-(x)))
    
    int Sum (int k)
    {
        int sum=0;
        while (k>0)
        {
            sum+=bit[k];
            k-=lowbit(k);
        }
        return sum;
    }
    
    void Update (int k,int val)
    {
        while (k<=s)
        {
            bit[k]+=val;
            k+=lowbit(k);
        }
    }
    
    void getnext ()
    {
    	int i=1,j=0,kk;
    	next[1]=0;
    	while (i<=k)
    		if (j==0 || (Sum(tt[i]-1)==m1[j] && Sum(tt[i])==m2[j]))
    		{
    			i++,j++;
    			next[i]=j;
    			if (i==k+1) return ;   //避免树状数组访问0
    			Update(tt[i],1);
    		}
    		else
    		{
    			for (kk=i-j+1;kk<=i-next[j];kk++)   //这里对next[j]之前的b[i]都要消除
    				Update(tt[kk],-1);
    			j=next[j];
    		}
    }
    
    int kmp ()
    {   //这里对待匹配串用树状数组记录
    	int i=1,j=1,kk;
    	Update(ss[1],1);
    	while (i<=n)
    	{
    		if (j==0 ||(Sum(ss[i]-1)==m1[j] && Sum(ss[i])==m2[j]))
    		{
    			++i,++j;
    			if (i<=n) Update(ss[i],1);
    		}
    		else
    		{
    			for (kk=i-j+1;kk<=i-next[j];kk++)
    				Update(ss[kk],-1);
    			j=next[j];
    		}
            if (j>k)
    		{
    			for (kk=i-j+1;kk<=i-next[j];kk++)
    				Update(ss[kk],-1);
    			cnt++;
    			ans[cnt]=i-1; //记录结尾位置
    			j=next[j];
    		}
    	}
    	return cnt;
    }
    
    void Init ()
    {
    	cnt=0;
    	memset(ss,0,sizeof(ss));
    	memset(tt,0,sizeof(tt));
    	memset(ans,0,sizeof(ans));
    	memset(next,0,sizeof(next));
    	memset(bit,0,sizeof(bit));
    	memset(m1,0,sizeof(m1));
    	memset(m2,0,sizeof(m2));
    }
    
    int main ()
    {
    	int i;
    	while (~scanf("%d%d%d",&n,&k,&s))
    	{
    		Init ();
    		for (i=1;i<=n;i++)
    			scanf("%d",&ss[i]);
    
    		for (i=1;i<=k;i++)
    		{
    			scanf("%d",&tt[i]);
    			Update(tt[i],1);
    			m1[i]=Sum(tt[i]-1);
    			m2[i]=Sum(tt[i]);
    		}
    		memset(bit,0,sizeof(bit));
    		getnext();
    
    		memset(bit,0,sizeof(bit));
    		kmp();
    		for (i=1;i<=cnt;i++)
    			ans[i]=ans[i]+1-k;
    
    		int sum=1,tmp=ans[1];
    		if (cnt==0) sum=0;     //
    		for (i=2;i<=cnt;i++)
    			if (ans[i]>=tmp+k)
    			{
    				sum++;
    				tmp=ans[i];
    			}
    		printf("%d\n",sum);
    	}
    	return 0;
    }

[poj 3167 - 1292765944_ - _ - CSDN.NET]: http://blog.csdn.net/waitfor_/article/details/7717059