QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#479454#552. 字符串匹配问题templatetemplate#0 18ms74316kbC++172.5kb2024-07-15 17:40:592024-07-15 17:41:00

Judging History

你现在查看的是最新测评结果

  • [2024-07-15 17:41:00]
  • 评测
  • 测评结果:0
  • 用时:18ms
  • 内存:74316kb
  • [2024-07-15 17:40:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &x){
	x=0;
	bool flag=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') flag=flag||(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	x=flag?-x:x;
}
template<typename T,typename ...Args>inline void read(T &x,Args &...args){
	read(x),read(args...);
}
template<typename T>inline void prt(T x){
	if(x>9) prt(x/10);
	putchar(x%10+'0');
}
template<typename T>inline void put(T x){
	if(x<0) putchar('-'),x=-x;
	prt(x);
}
template<typename T>inline void put(char ch,T x){
	put(x),putchar(ch);
}
template<typename T,typename ...Args>inline void put(char ch,T x,Args ...args){
	put(ch,x),put(ch,args...);
}
#define N 1100005
#define ld long double
const ld pi=acos(-1);
struct Complex{
	ld x,y;
	Complex(ld _x=0,ld _y=0):x(_x),y(_y){}
	inline Complex operator+(const Complex &b)const{return Complex(x+b.x,y+b.y);}
	inline Complex operator-(const Complex &b)const{return Complex(x-b.x,y-b.y);}
	inline Complex operator*(const Complex &b)const{return Complex(x*b.x-y*b.y,x*b.y+y*b.x);}
}f[N],g[N];
int rev[N];
inline void FFT(Complex *c,int len,int typ=1){
	for(int i=0;i<len;i++)
		if(i>rev[i]) swap(c[i],c[rev[i]]);
	for(int arc=1;arc<len;arc<<=1){
		Complex base=Complex(cos(typ*pi/arc),sin(typ*pi/arc));
		for(int i=0;i<len;i+=arc+arc){
			Complex now=Complex(1,0);
			for(int j=0;j<arc;j++,now=now*base){
				Complex x=c[i+j],y=c[i+j+arc]*now;
				c[i+j]=x+y,c[i+j+arc]=x-y;
			}
		}
	}
	if(typ==-1){
		for(int i=0;i<len;i++) c[i].x/=len;
	}
}
long long val[N];
int n,m,a[N],b[N];
char s[N],t[N];
int main(){
	scanf("%s%s",s,t),n=strlen(s)-1,m=strlen(t)-1;
	for(int i=0;i<=n;i++) a[i]=s[i]=='*'?0:s[i]-'a'+1;
	for(int i=0;i<=m;i++) b[i]=t[i]=='*'?0:t[i]-'a'+1;
	reverse(a,a+n+1);

	int len=1,bit=0;
	while(len<=n+m+1) len<<=1,bit++;
	for(int i=0;i<len;i++) rev[i]=rev[i>>1]>>1|(i&1)<<(bit-1);

	for(int i=0;i<len;i++) f[i]=g[i]=Complex();
	for(int i=0;i<=n;i++) f[i].x=a[i]*a[i];
	for(int i=0;i<=m;i++) g[i].x=b[i];
	FFT(f,len),FFT(g,len);
	for(int i=0;i<len;i++) f[i]=f[i]*g[i];
	FFT(f,len,-1);
	for(int i=0;i<=m;i++) val[i]+=(long long)(f[n+i].x+0.5);
	for(int i=0;i<len;i++) f[i]=g[i]=Complex();
	for(int i=0;i<=n;i++) f[i].x=a[i];
	for(int i=0;i<=m;i++) g[i].x=b[i]*b[i];
	FFT(f,len),FFT(g,len);
	for(int i=0;i<len;i++) f[i]=f[i]*g[i];
	FFT(f,len,-1);
	for(int i=0;i<=m;i++) val[i]-=(long long)(f[n+i].x+0.5);
	for(int i=0;i<=m-n;i++)
		if(!val[i]) put(' ',i+1);
	return 0;	
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 18ms
memory: 74316kb

input:

cabacacccbacccaabacacaabcabbabcaccbcabbacbcb
aaaccabacaaabb*abaaaa*bcabacacccba*ccaabacadaabcabba*kac*b*abbacabacacccbacccaa*acacaabcabbabca***cabbacbcbcabbacbcbbccbcacbaccbacaacc***bbbabccc**bbcbaaaaaabaabaacbc*cbcca*ccbabbacb*caaabcaba*acccbacccaabcabadac*cbacccaabacacaabca**abcucc*cxbbacb*bbacacc...

output:

56 64 65 80 84 141 164 166 255 258 418 423 424 426 444 450 451 453 477 487 494 495 506 591 607 685 702 792 794 817 825 844 870 910 

result:

wrong answer 1st numbers differ - expected: '64', found: '56'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%