No.1909 Detect from Substrings
レベル :
/ AI推定難易度 : 1600
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 73
作問者 :
chineristAC
/ テスター :
tokusakurai
ramdos
タグ : / 解いたユーザー数 73
作問者 :
chineristAC
/ テスター :
tokusakurai
ramdos
問題文最終更新日: 2022-04-08 00:14:08
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
yukicoder contest 340
(順位表)
の他の問題:
Problem Statement
You are given $N$ distinct strings $S_i\ (1\le i \le N)$ of length $M$ consisting of lowercase English letters.
Among strings $T$ of length $M+1$ consisting of lowercase English letters, find how many $T$ are such that every $S_i$ is a (not necessarily contiguous) subsequence of $T$.
Input
$N$ $M$ $S_1$ $S_2$ $\vdots$ $S_N$
- $2 \le N \le M $
- $4 \le NM \le 10^6 $
- $N,\ M$ are integers
- $S_i$ is a string of length $M$ consisting of lowercase English letters
- If $i\neq j$, then $S_i \neq S_j$
Output
Print the answer.
Print a newline at the end.
Sample
Sample 1
Input
2 3 abc bcd
Output
1
If $T=$abcd, then all $S_i$ are subsequences of $T$.
Sample 2
Input
4 4 abcd efgh ijkl mnop
Output
0
There is no $T$ such that all $S_i$ are its subsequences.
Sample 3
Input
2 2 ab ba
Output
2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。