{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e给定一个字符串 $$$t$$$ 和 $$$n$$$ 个字符串 $$$s_1, s_2, \\dots, s_n$$$。所有字符串均由小写拉丁字母组成。\u003c/p\u003e\u003cp\u003e设 $$$f(t, s)$$$ 表示字符串 $$$s$$$ 在字符串 $$$t$$$ 中出现的次数。例如,$$$f(\u0027\\text{aaabacaa}\u0027, \u0027\\text{aa}\u0027) \u003d 3$$$,$$$f(\u0027\\text{ababa}\u0027, \u0027\\text{aba}\u0027) \u003d 2$$$。\u003c/p\u003e\u003cp\u003e计算 $$$\\sum\\limits_{i\u003d1}^{n} \\sum\\limits_{j\u003d1}^{n} f(t, s_i + s_j)$$$ 的值,其中 $$$s + t$$$ 是字符串 $$$s$$$ 和 $$$t$$$ 的连接。请注意,如果存在两对 $$$i_1$$$,$$$j_1$$$ 和 $$$i_2$$$,$$$j_2$$$,使得 $$$s_{i_1} + s_{j_1} \u003d s_{i_2} + s_{j_2}$$$,则应在答案中同时包括 $$$f(t, s_{i_1} + s_{j_1})$$$ 和 $$$f(t, s_{i_2} + s_{j_2})$$$。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含字符串 $$$t$$$ ($$$1 \\le |t| \\le 2 \\cdot 10^5$$$)。\u003c/p\u003e\u003cp\u003e第二行包含整数 $$$n$$$ ($$$1 \\le n \\le 2 \\cdot 10^5$$$)。\u003c/p\u003e\u003cp\u003e接下来的 $$$n$$$ 行中,每行包含字符串 $$$s_i$$$ ($$$1 \\le |s_i| \\le 2 \\cdot 10^5$$$)。\u003c/p\u003e\u003cp\u003e保证 $$$\\sum\\limits_{i\u003d1}^{n} |s_i| \\le 2 \\cdot 10^5$$$。所有字符串均由小写英文字母组成。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出一个整数 — $$$\\sum\\limits_{i\u003d1}^{n} \\sum\\limits_{j\u003d1}^{n} f(t, s_i + s_j)$$$ 的值。\u003c/p\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003eaaabacaa\n2\na\naa\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003eaaabacaa\n4\na\na\na\nb\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e33\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}