SSttrriinngg in StringString

AtCoder

IDabc346_f

Time3000ms

Memory256MB

Difficulty—

For a string $X$ of length $n$, let $f(X,k)$ denote the string obtained by repeating $k$ times the string $X$, and $g(X,k)$ denote the string obtained by repeating $k$ times the first character, the second character, $\dots$, the $n$\-th character of $X$, in this order. For example, if $X=$ `abc`, then $f(X,2)=$ `abcabc`, and $g(X,3)=$ `aaabbbccc`. Also, for any string $X$, both $f(X,0)$ and $g(X,0)$ are empty strings. You are given a positive integer $N$ and strings $S$ and $T$. Find the largest non-negative integer $k$ such that $g(T,k)$ is a (not necessarily contiguous) subsequence of $f(S,N)$. Note that $g(T,0)$ is always a subsequence of $f(S,N)$ by definition. What is a subsequence? A (not necessarily contiguous) subsequence of a string $X$ is a string obtained by removing zero or more characters from $X$ and then concatenating the remaining elements without changing the order. For example, `ac`, `atcoder`, and (empty string) are all subsequences of `atcoder`, but `ta` is not. ## Constraints * $N$ is an integer. * $1\leq N\leq 10^{12}$ * $S$ and $T$ are strings consisting of lowercase English letters with lengths between $1$ and $10^5$, inclusive. ## Input The input is given from Standard Input in the following format: $N$ $S$ $T$ [samples]

Samples

Input #1

3
abc
ab

Output #1

2

We have $f(S,3)=$ `abcabcabc`. $g(T,2)=$ `aabb` is a subsequence of $f(S,3)$, but $g(T,3)=$ `aaabbb` is not, so print $2$.

Input #2

3
abc
arc

Output #2

Input #3

1000000000000
kzazkakxkk
azakxk

Output #3

344827586207

API Response (JSON)

{
  "problem": {
    "name": "SSttrriinngg in StringString",
    "description": {
      "content": "For a string $X$ of length $n$, let $f(X,k)$ denote the string obtained by repeating $k$ times the string $X$, and $g(X,k)$ denote the string obtained by repeating $k$ times the first character, the s",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc346_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "For a string $X$ of length $n$, let $f(X,k)$ denote the string obtained by repeating $k$ times the string $X$, and $g(X,k)$ denote the string obtained by repeating $k$ times the first character, the s...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments