欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Gym-101667H Rock Paper Scissors [FFT]

程序员文章站 2022-05-22 19:19:51
...

题意:给你两个字符串AB,简单处理后变为,求B在A中选一个起点开始匹配,能匹配到的位置的最大数量。

题解:枚举三种字符,对于每种字符,在某一位上出现时,该位为1,否则为0,字符匹配的O(n^2)过程,相当于卷积处理的过程,例如:

A串:PPPRRR

B串:RSSS

A处理:S变R,R变P,P变S

B处理:字符串翻转

A串:SSSPPP

B串:SSSR

对于S字符卷积的过程:

对于2这个位置:

Gym-101667H Rock Paper Scissors [FFT]

是这样的匹配,答案是3,但是这样的匹配是没有从B字符串的开始匹配的,也就是要从3这个位置开始匹配,所以是不符合的。

对于3这个位置:

Gym-101667H Rock Paper Scissors [FFT]

是满足字符串的匹配的,答案是2,所以对于卷积之后数组,我们只计算l2-1之后的答案。

对于三个字符分别计算后的答案,我们相同位置相加,得到的就是A与B的所有位置匹配的情况,最终答案去MAX即可。

AC代码:

#include<stdio.h>  
#include<string.h>  
#include<iostream>  
#include<algorithm>  
#include<math.h>  
#define MAXN 400005  
using namespace std;  
  
const double PI = acos(-1.0);  
//复数结构体  
struct complex  
{  
    double r,i;  
    complex(double _r = 0.0,double _i = 0.0)  
    {  
        r = _r; i = _i;  
    }  
    complex operator +(const complex &b)  
    {  
        return complex(r+b.r,i+b.i);  
    }  
    complex operator -(const complex &b)  
    {  
        return complex(r-b.r,i-b.i);  
    }  
    complex operator *(const complex &b)  
    {  
        return complex(r*b.r-i*b.i,r*b.i+i*b.r);  
    }  
};  
/* 
 * 进行FFT和IFFT前的反转变换。 
 * 位置i和 (i二进制反转后位置)互换 
 * len必须取2的幂 
 */  
void change(complex y[],int len)  
{  
    int i,j,k;  
    for(i = 1, j = len/2;i < len-1; i++)  
    {  
        if(i < j)swap(y[i],y[j]);  
        //交换互为小标反转的元素,i<j保证交换一次  
        //i做正常的+1,j左反转类型的+1,始终保持i和j是反转的  
        k = len/2;  
        while( j >= k)  
        {  
            j -= k;  
            k /= 2;  
        }  
        if(j < k) j += k;  
    }  
}  
/* 
 * 做FFT 
 * len必须为2^k形式, 
 * on==1时是DFT,on==-1时是IDFT 
 */  
void fft(complex y[],int len,int on)  
{  
    change(y,len);  
    for(int h = 2; h <= len; h <<= 1)  
    {  
        complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));  
        for(int j = 0;j < len;j+=h)  
        {  
            complex w(1,0);  
            for(int k = j;k < j+h/2;k++)  
            {  
                complex u = y[k];  
                complex t = w*y[k+h/2];  
                y[k] = u+t;  
                y[k+h/2] = u-t;  
                w = w*wn;  
            }  
        }  
    }  
    if(on == -1)  
        for(int i = 0;i < len;i++)
            y[i].r /= len;
}
complex x1[MAXN],x2[MAXN];
char A[MAXN/2],B[MAXN/2];  
int sum[MAXN],l1,l2,ans[MAXN]; 
void getans(char c)
{
    int len=1;  
    while(len<l1*2||len<l2*2)len<<=1;   
	for(int i=0;i<l1;i++)  
        x1[i]=complex(A[i]==c,0);  
    for(int i=l1;i<len;i++)  
        x1[i]=complex(0,0);  
    for(int i=0;i<l2;i++)  
        x2[i]=complex(B[i]==c,0);  
    for(int i=l2;i<len;i++)  
        x2[i]=complex(0,0);  
    //求DFT  
    fft(x1,len,1);  
    fft(x2,len,1);  
    for(int i=0;i<len;i++)  
        x1[i]=x1[i]*x2[i];  
    fft(x1,len,-1);  
    for(int i=0;i<len;i++)  
        sum[i]=(int)(x1[i].r+0.5);       
    len=l1+l2-1; 
    for(int i=0;i<len;i++)
    	ans[i]+=sum[i];
}
int main()  
{  
    scanf("%d%d%s%s",&l1,&l2,A,B); 
    for(int i=0;i<l1;i++)
    {
    	if(A[i]=='S')A[i]='R';
    	else if(A[i]=='R')A[i]='P';
    	else if(A[i]=='P')A[i]='S';
    }
    reverse(B,B+l2); 
    getans('S');
	getans('R');
	getans('P');
   	int ANS=0;
    for(int i=l2-1;i<l1+l2-1;i++)
    	ANS=max(ans[i],ANS);
   	printf("%d\n",ANS);
}  


相关标签: FFT