TopCoder

M_SQRT

User's AC Ratio

87.5% (7/8)

Submission's AC Ratio

77.8% (7/9)

Description

山姆有兩個由小寫英文字母構成的字串 $s,t$，他想知道兩個字串是不是相似的。他認為兩個字串相似，若兩字串間存在非空共同子字串。

因為字串的長度有可能很長，所以山姆希望你能幫他找出任意一個 $s,t$ 的非空共同子字串。

字串 $b$ 是字串 $a$ 的子字串若 $b$ 連續的出現在 $a$ 中。字串 $c$ 是字串 $a,b$ 的非空共同子字串若 $c$ 不是空字串而且 $c$ 既是 $a$ 的子字串，也是 $b$ 的子字串。

Input Format

輸入有兩行，第一行輸入字串 $s$，而第二行輸入字串 $t$。

$1\le |s|\le 10^ 6$，其中 $|s|$ 代表 $s$ 的長度。
$1\le |t|\le 10^ 6$，其中 $|t|$ 代表 $t$ 的長度。
所有字元皆為小寫英文字母（$\texttt{a}$ 到 $\texttt{z}$）。

Output Format

如果不存在任何非空共同子字串，則輸出一行 $\texttt{No}$。

否則輸出兩行。第一行輸出 $\texttt{Yes}$，而第二行則輸出任意一個 $s,t$ 的非空共同子字串。如果有不只一個非空共同子字串，請輸出任意一個。

Sample Input 1

looks
good

Sample Output 1

Yes
oo

Sample Input 2

hello
nsspc

Sample Output 2

Sample Input 3

abcdefghijklmnopqrstuvwxyz
abcdefghijklmnopqrstuvwxyz

Sample Output 3

Yes
abcdefghijklmnopqrstuvwxyz

Hints

Problem Source

No.	Testdata Range	Constraints	Score
1	0~2	範例測資	0
2	0~20	無額外限制	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	1000	524288	65536	1 2
1	1000	524288	65536	1 2
2	1000	524288	65536	1 2
3	1000	524288	65536	2
4	1000	524288	65536	2
5	1000	524288	65536	2
6	1000	524288	65536	2
7	1000	524288	65536	2
8	1000	524288	65536	2
9	1000	524288	65536	2
10	1000	524288	65536	2
11	1000	524288	65536	2
12	1000	524288	65536	2
13	1000	524288	65536	2
14	1000	524288	65536	2
15	1000	524288	65536	2
16	1000	524288	65536	2
17	1000	524288	65536	2
18	1000	524288	65536	2
19	1000	524288	65536	2
20	1000	524288	65536	2

863 . 字串中的字串