QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#92086 | #552. 字符串匹配问题 | Minion# | 0 | 0ms | 0kb | C++23 | 2.9kb | 2023-03-30 10:29:48 | 2023-03-30 10:29:49 |
Judging History
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%