Problem: F: Substring decomposition

problem

Given the two strings S and T and the integer k. Considering consecutive substrings of length k or more of T, determine if S can be constructed by concatenating them.

Where the string s = s_1 s_2 ... s_n is a contiguous substring s [l, r] = s_l s_ {l + 1} ... s_r (1 \ leq l \ leq r \ leq n) , S refers to a character string created by cutting out the l-th to r-th characters of s, and its length is r --l + 1.

Input format


S
T
k


Constraint

* S and T consist of lowercase alphabets
* 1 \ leq | S |, | T | \ leq 2 \ times 10 ^ 5
* 1 \ leq k \ leq | T |



Output format

Print `Yes` when S can be configured, and` No` on one line otherwise.

Input example 1


abracadabra
cadabra
Four


Output example 1


Yes

You can construct `abracadabra` by concatenating` abra` and `cadabra`, which are substrings of T with a length of 4 or more, which is a string equal to S.

Input example 2


abcd
zcba
1


Output example 2


No

Input example 3


abc
zcba
1


Output example 3


Yes

Input example 4


abcdefg
abcddefg
Four


Output example 4


No





Example

Input

abracadabra
cadabra
4


Output

Yes

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define SIZE 200005

int A_length,B_length,T_length,range;
int Rank[2*SIZE]; //接尾辞文字列の開始位置iの、辞書順にsortした際の順位表
int Suffix_Array[2*SIZE]; //接尾辞文字列の開始位置<インデックス>→毎回、辞書順に開始位置をソートする
int Work[2*SIZE];
int LCP[2*SIZE],LCP_Rank[2*SIZE];
int max_cover_length[SIZE];
int dp[SIZE];
char A[SIZE],B[SIZE],T[2*SIZE];

//まずrank[a]とrank[b]を比較、等しければrank[a+range],rank[b+range]を比較
bool compare_Suffix_Array(int a,int b){
	if(Rank[a] != Rank[b])return Rank[a] < Rank[b];
	else{
		int rank_a = a + range <= T_length ? Rank[a+range]:-1; //rangeを足した部分が範囲外なら、最高にするため、rankを-1にする
		int rank_b = b + range <= T_length ? Rank[b+range]:-1;
		return rank_a < rank_b;
	}
}

//文字列Tの接尾辞配列を構築
void make_Suffix_Array(){
	for(int i = 0; i <= T_length; i++){
		Suffix_Array[i] = i;
		Rank[i] = i < T_length? T[i]:-1; //初期ランクは文字コードにする。T[T_length]は空文字なので、最高となるように-1とする
	}

	//range,2*range,4*range,とソート幅を次第に伸ばしていく
	for(range = 1; range <= T_length; range*=2){
		sort(Suffix_Array,Suffix_Array+(T_length+1),compare_Suffix_Array); //range文字の幅でsuffix_Arrayをソート

		Work[Suffix_Array[0]] = 0;
		for(int i = 1; i <= T_length; i++){
			Work[Suffix_Array[i]] = Work[Suffix_Array[i-1]] + (compare_Suffix_Array(Suffix_Array[i-1],Suffix_Array[i])?1:0);
		}
		for(int i = 0; i <= T_length; i++){
			Rank[i] = Work[i];
		}
	}
}

void construct_LCP(){

	int n = T_length;
	for(int i = 0; i <= n; i++)LCP_Rank[Suffix_Array[i]] = i; //位置Suffix_Array[i]の配列上の位置を格納

	int h = 0;
	LCP[0] = 0;

	for(int i = 0; i < n; i++){
		//文字列中での位置iの接尾辞と、接尾辞配列中でその1つ前の接尾辞のLCPを求める
		int j = Suffix_Array[LCP_Rank[i]-1]; //LCP_Rank[n] == 0なので、マイナスになる心配はない

		//hを先頭の分1減らし、後ろが一致しているだけ増やす
		if(h > 0)h--;
		for(; j+h < n && i+h < n; h++){

			if(T[j+h] != T[i+h])break;
		}
		LCP[LCP_Rank[i]-1] = h;
	}
}


int main(){


	scanf("%s",A);
	for(A_length = 0; A[A_length] != '\0'; A_length++){

		T[A_length] = A[A_length];
	}
	T[A_length] = '@';
	T_length = A_length+1;

	scanf("%s",B);
	for(B_length = 0; B[B_length] != '\0'; B_length++,T_length++){

		T[T_length] = B[B_length];
	}

	int LEN;
	scanf("%d",&LEN);

	make_Suffix_Array();
	construct_LCP();

	int cover_length = 0;

	for(int i = 0; i <= T_length; i++){

		if(Suffix_Array[i] < A_length){

			max_cover_length[Suffix_Array[i]] = max(max_cover_length[Suffix_Array[i]],cover_length);
			cover_length = min(cover_length,LCP[i]);

		}else{

			cover_length = LCP[i];
		}
	}

	cover_length = 0;
	for(int i = T_length; i >= 1; i--){
		if(Suffix_Array[i] < A_length){

			max_cover_length[Suffix_Array[i]] = max(max_cover_length[Suffix_Array[i]],cover_length);
			cover_length = min(cover_length,LCP[i-1]);

		}else{

			cover_length = LCP[i-1];
		}
	}

	for(int i = 0; i <= A_length+1; i++){

		dp[i] = 0;
	}

	dp[0] = 1;
	dp[1] = -1;

	for(int i = 0; i <= A_length; i++){

		if(i > 0)dp[i] += dp[i-1];
		if(dp[i] == 0 || max_cover_length[i] < LEN || i == A_length)continue;

		dp[i+LEN]++;
		int right = min(A_length+1,i+max_cover_length[i]+1);
		dp[right]--;
	}

	if(dp[A_length] > 0){

		printf("Yes\n");
	}else{

		printf("No\n");
	}

	return 0;
}