부분 문자열 순열

두 문자열 $S$와 $P$가 주어졌을 때, $P$가 $S$의 부분 문자열로 나타나는지 판별하는 방법은 여러 가지가 있다. 가장 단순한 방법은 $P$가 $S$의 모든 부분 문자열과 같은지 직접 확인하는 것이다. 길이가 $|P|$인 $S$의 부분 문자열은 $O(|S|)$개 존재할 수 있으므로 이 방법의 시간 복잡도는 $O(|S| \times |P|)$이다. KMP(Knuth-Morris-Pratt) 알고리즘을 사용하면 $O(|S| + |P|)$에 해결할 수도 있다.

이 문제에서는 이와 비슷한 문제를 다룬다.

두 문자열 $S$와 $P$가 주어진다. $\Pi(S)$를 $S$의 순열(permutation)인 모든 문자열의 집합, $\Pi(P)$를 $P$의 순열인 모든 문자열의 집합이라고 하자. $\Pi(P)$의 원소 $p$와 $\Pi(S)$의 원소 $s$ 중에서 $p$가 $s$의 부분 문자열로 나타나는 쌍이 존재하는지 판별하라.

예를 들어 $S = \text{guru}$, $P = \text{rug}$라고 하자. 그러면 $\Pi(S) = \{\text{gruu}, \text{guru}, \text{guur}, \text{rguu}, \text{rugu}, \text{ruug}, \text{ugru}, \text{ugur}, \text{urgu}, \text{urug}, \text{uugr}, \text{uurg}\}$이고, $\Pi(P) = \{\text{gru}, \text{gur}, \text{rgu}, \text{rug}, \text{ugr}, \text{urg}\}$이다. $\Pi(P)$의 문자열 $\text{rug}$가 $\Pi(S)$의 문자열 $\text{rugu}$의 부분 문자열로 나타나는 것을 확인할 수 있다. 즉 $[\text{rug}]\text{u}$이다. 이 예에서는 $\langle\text{gru}, \text{gruu}\rangle$, $\langle\text{gru}, \text{ugru}\rangle$, $\langle\text{urg}, \text{uurg}\rangle$, $\langle\text{gur}, \text{guru}\rangle$ 등 조건을 만족하는 다른 쌍도 찾을 수 있다.

입력은 두 줄로 이루어진다. 첫 번째 줄에는 문자열 $S$가 주어진다 ($1 \le |S| \le 100000$). 두 번째 줄에는 문자열 $P$가 주어진다 ($1 \le |P| \le |S| \le 100000$). $S$와 $P$는 모두 알파벳 소문자(a-z)로만 이루어져 있다.

$\Pi(P)$의 원소 $p$와 $\Pi(S)$의 원소 $s$ 중에서 $p$가 $s$의 부분 문자열로 나타나는 쌍이 존재하면 “YES”를, 존재하지 않으면 “NO”를 큰따옴표 없이 한 줄에 출력한다.