#2310. 字符串
字符串
字符串
题目描述
CCF NOI 2024 四川省代表队评测活动 第一试 字符串(string) 字符串(string) 【题目描述】 给定 𝑛 个 𝑠 串,𝑚 个 𝑡 串。𝑓(𝑖, 𝑗, 𝑘, 𝑙) 表示 𝑠𝑖+ 𝑡𝑗 作为 𝑠𝑘+ 𝑡𝑙 的子串出现的次数,字符 串 𝑎+ 𝑏 表示将 𝑏 直接拼接在 𝑎 后面,求 ∑ 𝑛 𝑖=1 ∑ 𝑚 𝑗=1 ∑ 𝑛 𝑘=1 ∑ 𝑚 𝑙=1 𝑓(𝑖, 𝑗, 𝑘, 𝑙) 的值。由于答案很大,请输出其对 109 + 7 取模后的值。 对于字符串 𝑎, 𝑏,字符串 𝑎+ 𝑏 表示将 𝑏 直接拼接在 𝑎 的后面。例如:若字符串 𝑎 为 abc,字符串 𝑏 为 ab,则字符串 𝑎+ 𝑏 为 abcab。 对于非空字符串 𝑎, 𝑏,如果将 𝑎 删去某个前缀和某个后缀(可以为空)后与 𝑏 相同,则称 𝑏 为 𝑎 的子串。例如:对于字符串 abcd,字符串 a,bcd,bc 均是这个字符串的子串,而字 符串 acd,bd 不是这个字符串的子串。 【输入格式】 从文件 string.in 中读入数据。 输入的第一行包含两个整数 𝑛 和 𝑚。 接下来 𝑛 行,每行包含一个只由小写英文字母组成的字符串 𝑠𝑖。 接下来 𝑚 行,每行包含一个只由小写英文字母组成的字符串 𝑡𝑗。 【输出格式】 输出到文件 string.out 中。 输出一行一个整数,表示答案对 109 + 7 取模后的值。 【样例1 输入】 1 2 3 2 a 3 ba 4 b 5 bb 6 ab 【样例1 输出】 第2 页 共9 页
CCF NOI 2024 四川省代表队评测活动 第一试 字符串(string) 1 14 【样例2】 见选手目录下的 string/string2.in 与 string/string2.ans。 这个样例满足测试点 3 ∼6 的条件限制。 【样例3】 见选手目录下的 string/string3.in 与 string/string3.ans。 这个样例满足测试点 9 ∼12 的条件限制。 【样例4】 见选手目录下的 string/string4.in 与 string/string4.ans。 这个样例满足测试点 13 ∼20 的条件限制。 【数据范围】 对于所有测试数据保证:1 ≤𝑛, 𝑚≤105,1 ≤|𝑠𝑖|, |𝑡𝑗| ≤106,∑|𝑠𝑖|, ∑|𝑡𝑗| ≤106。 测试点编号 𝑛 𝑚 |𝑠𝑖|, |𝑡𝑖|, ∑|𝑠𝑖|, ∑|𝑡𝑗| 特殊性质 1 ∼2 ≤50 ≤50 ≤100 无 3 ∼6 ≤200 ≤200 ≤103 7 ∼8 ≤105 ≤105 ≤106 A 9 ∼12 = 1 无 13 ∼20 ≤105 特殊性质 A: 所有 𝑠 串只包含一种字母,所有 𝑡 串只包含与 𝑠 串不同的另一种字母。 第3 页 共9 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
2 3
a
ba
b
bb
ab
14
样例 2
137 112
t
lw
hdvp
otceea
t
d
yt
fgphf
prxakk
cycre
au
orh
drwgj
kngzgq
qsm
jwawx
qtjq
tpkex
ovo
dyyqo
wphonp
zvu
zvsom
fw
wm
m
ymhxhl
ms
gq
fcblyf
ju
zl
b
sauha
wc
u
d
gmhgtp
qgne
xwc
zk
v
jjzy
nwumsk
lj
eq
qtku
zdjrc
v
en
oqic
dnjze
eis
bgtoi
z
hqfcco
lkiv
qf
jni
k
lwgao
ex
lda
org
aw
b
ge
sfug
szsohv
qhloi
iiqx
cahmrb
kj
lfrf
z
k
wuz
yox
vr
kiqv
tmznq
eyw
s
e
dm
cm
aapekm
sfqa
l
m
ldmypv
tnbehd
cckos
ggqrfg
vii
ffhof
jobt
nlojdd
dwbd
qfafso
h
guka
oseyh
wxhk
mrhht
ytamg
tawfjw
munwg
ss
u
rctzn
ltw
p
hqtltp
gyw
lfbpt
cw
nt
k
wnh
simqr
lygaq
b
sxhuo
ea
bqyvw
cv
e
dqw
sbll
zu
men
azihh
wbhce
fwh
smn
avshpzjxbbnugvgubbvrsglsdtcdakabfafoilmyqaajyvzodeaznygtkzzaibwgbthndpcptasiczarotjuyiyosywejavkvwbxgflhbjhfgxwkhfgyxeckuaqdomvzqtwfrklobiehapbhbonlvemvwsfdmjdzfbmjlxxapigrsauugbqzuztakpvbbzgmqsnnymthcpfgaectobafhqssaljfbbwtsrrshvsomjenxtfasbuojewztyixnmorlikxyzssfpkovtvjknsxnubwozpiribwcwbithqxnqakhdzlvlkcvblckfdldwbnyrigegmjfpuhlcaolsmafpjupbufcztlrfnpkrrohrswahxudlcxifsujcctnfzwellmzasitkxtzlstiyaswytwklujhgdsmjkbvvkgjewxivxskvdoulvjkculqnkdlkvcmkwsiansgulyutmenzidfcahzibegbwjdoudxtnyteplemugtqpekgezdagsjszqkrsuwagnaaswubfnissgvr
sxgxefx
c
tx
erv
nkytrai
iuoeswy
vhx
k
zxnlkky
ypzelz
ng
cdk
edfsg
noojgqu
x
dhgvasj
jdsvpb
hzihtb
hd
hjt
ih
enjpyo
zvwat
tvb
i
okvpsd
d
hw
yxkkim
s
hx
ixoc
dx
qk
eqpykzu
cnpxid
uqxpo
xzyxr
uypd
joucmza
bcnlyt
w
ljpn
x
igzp
zj
oys
bgluoj
kdrpdp
gkfuz
wnyope
q
tjtysy
x
uoguxv
fexo
hc
nk
yrxbnv
p
rybllcc
attuxh
d
pmoxg
fxc
xvkpvo
yxbu
lmpsn
bux
gubtoao
bumqann
s
eknyoh
dbka
fmxr
kuoyes
rtprhh
ax
cte
qneuu
ecse
m
dastfba
j
dyglml
hqyau
iyl
tkrsk
hghpmta
dtp
d
rcpatm
xvya
u
b
nukmw
oyomli
aqg
wy
n
zdzho
rqon
t
pb
jdz
tcwbx
dohad
dyzaozv
deua
iooiphy
kots
okdrpzzefjeiwvqiggoywkeaemfujsqsdgiphcrdbpppcctzsgkszrrfuiuoxsptafisjeqpatujwxgyayqvsqywbjvamairtxvbsowdcrygfzbmfpbgpdavmoxdczuluuzzjuoyrwwnxsevhdxmrnwhjuihaurjhywzbydulhsswbccrvlvslltdtavtrawudrflfjokagkxisifqpikskizersrwonvqwrqrtokvehwucjdsynluncvrcvtdtckilrzweoduildixrtouactusqkopfyxyiugtmuvbevseqoymdhoadvlvicbozdbcipzzznkqpkmbadragdvkfbejuoahxlnfkudhnfqzlohlayoxxuobovaocdhhhqcfgstpoinmflporcgkfvlmgimooshsjowubpxyjmxznexhfglwbtqxnicaptehwbiizagahugrsgdksqvrzlokgizcwzwbamgfufyouwafwhfzqeangzuuafpfbavvvmqwabtxwqwjmvkrohumhgsakmfulpycogykbydjhwvgja
213260