QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#92086#552. 字符串匹配问题Minion#0 0ms0kbC++232.9kb2023-03-30 10:29:482023-03-30 10:29:49

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-30 10:29:49]
  • Judged
  • Verdict: 0
  • Time: 0ms
  • Memory: 0kb
  • [2023-03-30 10:29:48]
  • Submitted

answer

#include<cstdio>
#include<vector>
#define fo(i,x,y) for(int i = x;i <= y;++i)
#define fd(i,x,y) for(int i = x;i >= y;--i)
#define _is 1048576
#define _os 1048576 * 4
#define gc() ib[++bi]
#define pc(ch) ob[++bo] = ch
#define ist(ch) (ch >= 'a' && ch <= 'z' || ch == '*')
#define sz(x) int(x.size())
#define add(x,y) (x >= p - y ? x + y - p : x + y)
#define sub(x,y) (x < y ? x - y + p : x - y)
#define p 998244353
using namespace std;
char ib[_is],ob[_os];int bi = -1,bo = -1;
int rd()
{
	int x = 0;char ch = gc();
	while(ch < 48 || ch > 57) ch = gc();
	while(ch >= 48 && ch <= 57) x = x * 10 + ch - 48,ch = gc();return x;
}
void gs(char *s)
{
	int l = -1;char ch = gc();
	while(ist(ch) == 0) ch = gc();
	while(ist(ch)) s[++l] = ch,ch = gc();
	s[++l] = 0;
}
void pr(int x,char s)
{
	if(x < 0) pc('-'),x = -x;
	char ch[20];int w = -1;
	if(x == 0) ch[++w] = 48;
	while(x) ch[++w] = x % 10 + 48,x /= 10;
	fd(i,w,0) pc(ch[i]);pc(s);
}
int n,m,r[1000010],w[1050010];
char s1[1000010],s2[1000010];
int ksm(int x,int y)
{
	int res = 1;
	for(;y;y >>= 1,x = 1ll * x * x % p) if(y & 1) res = 1ll * res * x % p;
	return res;
}
void pre(int N,int lg)
{
	w[0] = 1,w[1ll << (lg - 1)] = ksm(3,(p - 1) >> (lg + 1));
	fd(i,lg - 1,1) w[1ll << (i - 1)] = 1ll * w[1ll << i] * w[1ll << i] % p;
	fo(i,1,1 << (lg - 1)) w[i] = 1ll * w[i & i - 1] * w[i & -i] % p;
}
struct poly
{
	vector<int> a;
	poly() {}
	poly(int sz) {a.resize(sz);}
	poly(poly &b) {a = b.a;}

	int &operator [](int x) {return a[x];}
	void resize(int x) {a.resize(x);}
	void clear() {a.clear(),a.shrink_to_fit();}
	int size() {return a.size();}
	void DIF()
	{
		int N = sz(a);
		for(int l = N >> 1;l;l >>= 1) for(int i = 0,k = 0;i < N;i += l << 1,++k) fo(j,0,l - 1)
		{
			int x = a[i + j],y = 1ll * a[i + j + l] * w[k] % p;
			a[i + j] = add(x,y),a[i + j + l] = sub(x,y);
		}
	}
	void DIT()
	{
		int N = sz(a);
		for(int l = 1;l < N;l <<= 1) for(int i = 0,k = 0;i < N;i += (l << 1),++k) fo(j,0,l - 1)
		{
			int x = a[i + j],y = a[i + j + l];
			a[i + j] = add(x,y),a[i + j + l] = 1ll * sub(x,y) * w[k] % p;
		}
		fo(i,1,(N - 1) >> 1) a[i] ^= a[N - i] ^= a[i] ^= a[N - i];
		int ny = ksm(N,p - 2);
		fo(i,0,N - 1) a[i] = 1ll * a[i] * ny % p;
	}
};
int main()
{
	fread(ib,1,_is,stdin);
	m = rd(),n = rd(),gs(s2),gs(s1);
	int N = 1,lg = 0;
	while(N < n) N <<= 1,++lg;
	pre(N,lg);
	poly c(N);
	fo(id,'a','z')
	{
		poly a(N),b(N);
		fo(i,0,n - 1) a[i] = s1[i] == '*' || s1[i] == id;
		fo(i,0,m - 1) b[m - i - 1] = s2[i] == '*' || s2[i] == id;
		a.DIF(),b.DIF();
		fo(i,0,N - 1) c[i] = (c[i] + 1ll * a[i] * b[i]) % p;
	}
	poly a(N),b(N); 
	fo(i,0,n - 1) a[i] = (s1[i] == '*') * (p - 25);
	fo(i,0,m - 1) b[m - i - 1] = s2[i] == '*';
	a.DIF(),b.DIF();
	fo(i,0,N - 1) c[i] = (c[i] + 1ll * a[i] * b[i]) % p;
	c.DIT();
	int ans = 0;
	fo(i,m - 1,n - 1) ans += c[i] == m;
	pr(ans,'\n');
	fo(i,m - 1,n - 1) if(c[i] == m) pr(i - m + 2,' ');
	fwrite(ob,1,bo + 1,stdout);
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

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%