QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#125881#552. 字符串匹配问题cp152#0 0ms0kbC++141.6kb2023-07-17 20:46:402023-07-17 20:46:43

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-17 20:46:43]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2023-07-17 20:46:40]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int M=1048576;
unsigned seed=186164;
unsigned long long rnd()
{
	seed^=seed<<7;
	seed^=seed>>11;
	seed^=seed<<17;
	return seed;
}
char c[M+5],d[M+5];
int f[M+5],g[M+5];
int f2[M+5],g2[M+5];
int f3[M+5],g3[M+5];
int hsh[26];
int n,m;
const int mod=998244353,inv3=332748118;
int tr[M+5];
int pw(int a,int b=mod-2)
{
	int re=1;
	while(b)
	{
		if(b&1)	re=1ll*re*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return re;
}
void NTT(int f[],int len,bool b)
{
	for(int i=1;i<len;i++)	tr[i]=(tr[i>>1]>>1)|((i&1)?(len>>1):0);
	for(int i=0;i<len;i++)	if(tr[i]<i)	swap(f[i],f[tr[i]]);
	for(int i=1;i<len;i*=2)
		for(int j=0;j<len;j+=2*i)
		{
			int yg=pw(b?3:inv3,mod/i/2),dwg=1;
			for(int k=0;k<i;k++)
			{
				int tmp=f[j+k];
				f[j+k]=(f[j+k]+1ll*f[i+j+k]*dwg)%mod;
				f[i+j+k]=(tmp-1ll*f[i+j+k]*dwg)%mod;
				dwg=1ll*dwg*yg%mod;
			}
		}
	if(b)
	{
		int tmp=pw(len);
		for(int i=0;i<len;i++)	f[i]=1ll*f[i]*tmp%mod;
	}
}
int main()
{
	for(int i=0;i<26;i++)	hsh[i]=rnd()%mod;
	scanf("%s",c);
	scanf("%s",d);
	for(n=0;c[n];n++);
	for(m=0;d[m];m++);
	for(int i=n-1;~i;i--)	f[n-1-i]=(c[i]=='*'?0:hsh[c[i]-'a']);
	for(int i=0;i<m;i++)	g[i]=(d[i]=='*'?0:hsh[d[i]-'a']);
	for(int i=0;i<n;i++)	f2[i]=1ll*f[i]*f[i]%mod,f3[i]=1ll*f2[i]*f[i]%mod;
	for(int i=0;i<m;i++)	g2[i]=1ll*g[i]*g[i]%mod,g3[i]=1ll*g2[i]*g[i]%mod;
	NTT(f,M,0);
	NTT(g,M,0);
	NTT(f2,M,0);
	NTT(g2,M,0);
	NTT(f3,M,0);
	NTT(g3,M,0);
	for(int i=0;i<M;i++)	f[i]=(1ll*f[i]*g3[i]-2ll*f2[i]*g2[i]+1ll*f3[i]*g[i])%mod;
	NTT(f,M,1);
	for(int i=n-1;i<m;i++)	
	{
		if(!f[i])	cout<<i-n+2<<' ';
	}
	return 0;
}

詳細信息

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%