Substring Permutation

Given two strings $S$ and $P$, there are several ways to determine whether $P$ appears as a substring of $S$. The simplest is to check directly whether $P$ equals any substring of $S$. Since $S$ can have $O(|S|)$ substrings of length $|P|$, this approach takes $O(|S| \times |P|)$ time. A more sophisticated method uses the Knuth-Morris-Pratt (KMP) algorithm to solve the problem in $O(|S| + |P|)$.

This problem poses a similar challenge.

Given two strings $S$ and $P$. Let $\Pi(S)$ be the set of all strings that are permutations of $S$, and $\Pi(P)$ the set of all strings that are permutations of $P$. Determine whether there exists a string $p \in \Pi(P)$ and a string $s \in \Pi(S)$ such that $p$ appears as a substring of $s$.

For example, let $S = \text{guru}$ and $P = \text{rug}$. Then $\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}\}$, and $\Pi(P) = \{\text{gru}, \text{gur}, \text{rgu}, \text{rug}, \text{ugr}, \text{urg}\}$. The string $\text{rug}$ in $\Pi(P)$ appears as a substring of the string $\text{rugu}$ in $\Pi(S)$, that is, $[\text{rug}]\text{u}$. In this example you can also find other pairs that satisfy the requirement, such as $\langle\text{gru}, \text{gruu}\rangle$, $\langle\text{gru}, \text{ugru}\rangle$, $\langle\text{urg}, \text{uurg}\rangle$, $\langle\text{gur}, \text{guru}\rangle$.

The input consists of two lines. The first line contains a string $S$ ($1 \le |S| \le 100000$). The second line contains a string $P$ ($1 \le |P| \le |S| \le 100000$). Both $S$ and $P$ consist only of lowercase English letters (a-z).

If there exists a string $p \in \Pi(P)$ and a string $s \in \Pi(S)$ such that $p$ appears as a substring of $s$, output “YES” on one line. Otherwise, output “NO”. Do not print the quotes.