/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 525 点
問題文
長さ n の文字列 X に対して、X を k 回繰り返して得られる文字列を f(X,k) と表記し、X の 1 文字目、2 文字目、\dots、n 文字目を k 回ずつこの順に繰り返して得られる文字列を g(X,k) と表記します。
例えば、X= abc のとき、f(X,2)= abcabc、g(X,3)= aaabbbccc です。
また、任意の文字列 X に対して、f(X,0) と g(X,0) は共に空文字列です。
正整数 N および文字列 S,T が与えられます。 g(T,k) が f(S,N) の（連続とは限らない）部分列であるような最大の非負整数 k を求めてください。 なお、定義より、g(T,0) は常に f(S,N) の部分列であることに注意してください。
部分列とは
文字列 X の（連続とは限らない）部分列とは、X から 0 個以上の文字を取り除いた後、残りの文字を元の順序で連結して得られる文字列のことをいいます。 例えば、ac、atcoder、 （空文字列）などはどれも atcoder の部分列ですが、ta は atcoder の部分列ではありません。
制約
- N は整数
- 1\leq N\leq 10^{12}
- S, T は英小文字からなる長さ 1 以上 10^5 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S T
出力
g(T,k) が f(S,N) の（連続とは限らない）部分列であるような最大の非負整数 k を出力せよ。
入力例 1
3 abc ab
出力例 1
2
f(S,3)= abcabcabc です。
g(T,2)= aabb は f(S,3) の部分列ですが、g(T,3)= aaabbb は f(S,3) の部分列ではないので、2 を出力します。
入力例 2
3 abc arc
出力例 2
0
入力例 3
1000000000000 kzazkakxkk azakxk
出力例 3
344827586207
Score: 525 points
Problem Statement
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
Output
Print the largest non-negative integer k such that g(T,k) is a (not necessarily contiguous) subsequence of f(S,N).
Sample Input 1
3 abc ab
Sample 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.
Sample Input 2
3 abc arc
Sample Output 2
0
Sample Input 3
1000000000000 kzazkakxkk azakxk
Sample Output 3
344827586207