链接
点击跳转
题解
这个
f
f
f函数其实很容易等于
0
0
0的，如果
s
s
s不是
t
t
t的子串，这个函数就等于
0
0
0了
而他让求的是一个乘法式子，乘法式子中只要有一项等于
0
0
0，整个式子就等于
0
0
0了
而我们知道，一个串不可能成为比他还短的串的子串，所以只有最短的串的答案才不等于
0
0
0
进一步分析，如果最短串有好几种，那么最短串的答案也等于
0
0
0了
所以只有当最短串只有一种的时候(就是说所有最短串都长得一样)，才需要计算答案
那么就很简单了，直接
k
m
p
kmp
kmp即可
最直接的想法是每次把一个其它串接在最短串的后面然后
k
m
p
kmp
kmp，并且我每次只计算新拼接上这一部分的
n
e
x
t
next
next，但是为了偷懒，其实我完全可以每次计算整个串的
n
e
x
t
next
next，可以证明这么做的时间复杂度依然是线性的
代码
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define iinf 0x3f3f3f3f
#define linf (1ll<<60)
#define eps 1e-8
#define maxn 4000010
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define de(x) cerr<<#x<<" = "<<x<<endl
using namespace std
;
using namespace __gnu_pbds
;
typedef long long ll
;
typedef pair
<int,int> pii
;
typedef pair
<ll
,ll
> pll
;
ll
read(ll x
=0)
{
ll c
, f(1);
for(c
=getchar();!isdigit(c
);c
=getchar())if(c
=='-')f
=-f
;
for(;isdigit(c
);c
=getchar())x
=x
*10+c
-0x30;
return f
*x
;
}
struct KMP
{
int n
, next
[maxn
], t
[maxn
];
void build(const char *r
, int len
)
{
int i
, j
=0;
n
=len
;
for(i
=1;i
<=len
;i
++)t
[i
]=r
[i
]; t
[len
+1]=0;
for(i
=2;i
<=len
;i
++)
{
for(;j
and t
[j
+1]!=t
[i
];j
=next
[j
]);
next
[i
] = t
[j
+1]==t
[i
]?++j
:0;
}
}
}kmp
;
#define mod 998244353ll
char r
[maxn
];
int main()
{
ll n
=read(), mn
=linf
, i
, j
;
vector
<string
> s(n
+5);
rep(i
,1,n
)
{
cin
>>s
[i
];
mn
= min(mn
,(ll
)s
[i
].length());
}
ll ans
;
unordered_set
<string
> S
;
rep(i
,1,n
)if(s
[i
].length()==mn
)S
.insert(s
[i
]);
if(S
.size()>1)
{
ans
=0;
}
else
{
ans
= 1;
string t
;
string ss
= *S
.begin();
rep(i
,1,n
)
{
t
= ss
+ '|' + s
[i
];
kmp
.build(t
.c_str()-1,t
.length());
ll cnt
=0;
rep(j
,ss
.length()+2,kmp
.n
)cnt
+=(kmp
.next
[j
]==ss
.length());
(ans
*= cnt
)%=mod
;
}
}
rep(i
,1,n
)
{
if(s
[i
].length()==mn
)
{
printf("%lld\n",ans
);
}
else printf("0\n");
}
return 0;
}
