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>
#define whlie while
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define rep(i,N) for(int i = 0; i < (N); i++)
#define repr(i,N) for(int i = (N) - 1; i >= 0; i--)
#define rep1(i,N) for(int i = 1; i <= (N) ; i++)
#define repr1(i,N) for(int i = (N) ; i > 0 ; i--)
#define each(x,v) for(auto& x : v)
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define vrep(v,it) for(auto it = v.begin(); it != v.end(); it++)
#define vrepr(v,it) for(auto it = v.rbegin(); it != v.rend(); it++)
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
using namespace std; void solve();
using ll = long long; using vl = vector<ll>;
using vi = vector<int>; using vvi = vector< vector<int> >;
constexpr int inf = 1001001001;
constexpr ll infLL = (1LL << 61) - 1;
struct IoSetupNya {IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7);} } iosetupnya;
template<typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template<typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; }
template<typename T, typename U> ostream& operator <<(ostream& os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; }
template<typename T, typename U> istream& operator >>(istream& is, pair<T, U> &p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator <<(ostream& os, const vector<T> &v) { int s = (int)v.size(); rep(i,s) os << (i ? " " : "") << v[i]; return os; }
template<typename T> istream& operator >>(istream& is, vector<T> &v) { for(auto &x : v) is >> x; return is; }
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
template<typename T>void die(T x){out(x); exit(0);}
#ifdef NyaanDebug
  #include "NyaanDebug.h"
  #define trc(...) do { cerr << #__VA_ARGS__ << " = "; dbg_out(__VA_ARGS__);} while(0)
  #define trca(v,...) do { cerr << #v << " = "; array_out(v , __VA_ARGS__ );} while(0)
#else
  #define trc(...)
  #define trca(...)
  int main(){solve();}
#endif

constexpr int MOD = /** 1000000007; //*/ 998244353;
/////////////////

// Suffix Array
//verify https://judge.yosupo.jp/submission/240
struct SuffixArray{
  int _size;
  vector<int> sa;
  string &s;
  SuffixArray(string &str):_size(str.size()) , s(str) {
    // うしさんのO( N logN )の実装
    s.push_back(0);
    sa.resize(s.size());
    iota(begin(sa), end(sa), 0);
    sort(begin(sa), end(sa), [&](int a, int b) {
      return s[a] == s[b] ? a > b : s[a] < s[b];
    });
    vector< int > classes(s.size()), c(s.begin(), s.end()), cnt(s.size());
    for(int len = 1; len < (int)s.size(); len <<= 1) {
      for(int i = 0; i < (int)s.size(); i++) {
        if(i > 0 && c[sa[i - 1]] == c[sa[i]] && sa[i - 1] + len < (int)s.size() && c[sa[i - 1] + len / 2] == c[sa[i] + len / 2]) {
          classes[sa[i]] = classes[sa[i - 1]];
        } else {
          classes[sa[i]] = i;
        }
      }
      iota(begin(cnt), end(cnt), 0);
      copy(begin(sa), end(sa), begin(c));
      for(int i = 0; i < (int)s.size(); i++) {
        int s1 = c[i] - len;
        if(s1 >= 0) sa[cnt[classes[s1]]++] = s1;
      }
      classes.swap(c);
    }
    s.pop_back();
  }
  // デバッグ用に実装
  void output() {
    cout << "SA\tidx\tstr" << endl;
    for(int i = 0; i < size(); i++) {
      cout << i << ": \t" << sa[i] << " \t" ;
      if(sa[i] != _size) cout << s.substr(sa[i],_size - sa[i]) << endl;
      else cout << "$" << endl;
    }
    cout << endl;
  }
  // sa.size()と表せると便利なので実装
  int size() const{return _size + 1;}
  // sa[]と表せると便利なのでオーバーロードしておく
  int operator[](int k) const{return sa[k]; }
};

struct LCPArray {
  const SuffixArray &SA;
  vector<int> LCP, rank;
  LCPArray(const SuffixArray &sa) : SA(sa) {
    LCP.resize(SA.size()); rank.resize(SA.size());
    // 初期化　rankはsaの逆関数
    for(int i = 0; i < SA.size(); i++) {
      rank[SA[i]] = i;
    }
    LCP[0] = 0; 
    
    // 構築
    for(int i = 0, h = 0; i < SA.size() - 1 ; i++) {
      int j = SA[rank[i] - 1] ; h ? h-- : h;
      // ここで尺取り法に近い手法を使うことでO(N)でLCPの構築をしている
      while( (i > j ? i : j) + h < SA.size() - 1 && SA.s[i + h] == SA.s[j + h] && ++h );
      LCP[rank[i] - 1] = h;
    }
  }

  // デバッグ用に実装
  void output() {
    cout << "SA\tidx\tLCP\tstr" << endl;
     for(int i = 0 ; i < SA.size() ; i++){
      cout << i << "\t" << SA[i] <<" \t" << LCP[i] << "\t"; 
      if(SA[i] == SA.size() - 1) cout << "$";
      else cout << SA.s.substr(SA[i] , SA.size() - 1 - SA[i]);
      cout << endl;
    }
  }

};

// Sparse Table
template<typename T>
struct SparseTable{
  vector< vector< T > > table;
  vector< int > log_table;

  SparseTable(const vector< T > &v) {
    int b = 0;
    while((1 << b) <= (int)v.size()) ++b;
    table.assign(b, vector< T >(1 << b));
    for(int i = 0; i < (int)v.size(); i++) {
      table[0][i] = v[i];
    }
    for(int i = 1; i < b; i++) {
      for(int j = 0; j + (1 << i) <= (1 << b); j++) {
        table[i][j] = min(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
      }
    }
    log_table.resize(v.size() + 1);
    for(int i = 2; i < (int)log_table.size(); i++) {
      log_table[i] = log_table[i >> 1] + 1;
    }
  }

  // 区間 [l , r) の最小値を返す
  inline T query(int l, int r) {
    int b = log_table[r - l];
    return min(table[b][l], table[b][r - (1 << b)]);
  }
};

// 文字列検索 検索 O(M + logN) メモリO(N logN)
// verify
// https://onlinejudge.u-aizu.ac.jp/status/users/NyaanNyaan/submissions/1/ALDS1_14_D/judge/3874273/C++14
// https://atcoder.jp/contests/abc135/submissions/7574225
// https://judge.yosupo.jp/submission/241
// https://atcoder.jp/contests/abc141/submissions/7577295
struct StringSearch{
  string &s;
  const SuffixArray &sa;
  const LCPArray &lcp;
  SparseTable<int> sparse;
  StringSearch(LCPArray &lcp)
    : s(lcp.SA.s) , sa(lcp.SA) , lcp(lcp) , sparse(lcp.LCP){ }

 // 文字列sの[i , N)と[j , N)の共通接頭辞の長さを求める
  int ArbitaryLCP(int i , int j){
    if(i == j) return (int)(s.size()) - i;
    return sparse.query(
      min(lcp.rank[i] , lcp.rank[j]) , 
      max(lcp.rank[i] , lcp.rank[j])  
    );
  }

  pair<int,int> comp(const string &t  , int len , int si , int ti = 0){
    int sn = (int)s.size() , tn = (int) t.size();
    si += len , ti += len;
    while(si < sn && ti < tn){
      if(s[si] != t[ti]) return make_pair( s[si]<t[ti] , ti);
      si++ , ti++;
    }
    return make_pair( (si>=sn && ti<tn) , ti);
  }  

  pair<int,int> find_range(int left , int med , int right , int len){
    {
      int ng = left - 1, ok = med;
      whlie(ng + 1 < ok){
        int cur = (ng + ok) / 2;
        if(sparse.query(cur , med) >= len) ok = cur;
        else ng = cur;
      }
      left = ok;
    }
    {
      int ok = med , ng = right + 1;
      whlie(ok + 1 < ng){
        int cur = (ng + ok) / 2;
        if(sparse.query(med, cur) >= len) ok = cur;
        else ng = cur;
      }
      right = ok;
    }
    return make_pair(left , right);
  }

  // 全ての出現範囲をSA上の[left , right]の範囲で返す
  // 存在しない場合は-1を返す
  pair<int,int> find(string &t){
    // 条件を満たす[left , right]を見つける
    // sa[0]は空文字列なので left = 1 とする
    // lenは既に一致している文字列の長さ
    int left = 1 , right = sa.size() - 1 , med = left;
    int leftlen = 0 , rightlen = 0 , tlen = t.size();
    pair<int,int> ret;
    while(left + 1 < right){
      med = (left + right) / 2;

      int corres_len = max(
        min(leftlen , sparse.query(left , med)) ,
        min(rightlen, sparse.query(med , right))
      );
      if(corres_len < max(leftlen , rightlen)){
        if(leftlen < rightlen) 
          left = med , leftlen = corres_len;
        else
          right= med ,rightlen = corres_len;
        continue;
      }
      ret = comp(t , corres_len , sa[med]);
      //trc(left,med,right,ret);
      if(ret.second == tlen)
        return find_range(left,med,right,tlen);
      if(ret.first == 0)
        right = med , rightlen = ret.second;
      else
        left = med , leftlen = ret.second;
    }
    if(sa.size() <= 3){
      if(comp(t,0,sa[left]).second==tlen) return find_range(left,left,right,tlen);
      if(comp(t,0,sa[right]).second==tlen) return find_range(left,right,right,tlen);
      return make_pair(-1,-1);
    }
    med = left + right - med;
    ret = comp(t , min(leftlen,rightlen) , sa[med]);
    //trc(left,med,right,ret);
    if(ret.second == tlen)
      return find_range(left,med,right,tlen);
    return make_pair(-1,-1);
  }
};

// Suffix Arrayの使い方(メモリを食うので必要なものだけ使う)
// 参照があるのでstringを削除などしないこと
/*
  SuffixArray sa(S);
  LCPArray lcp(sa);
  StringSearch search(lcp);
*/
// BIT

template< typename T >
struct BIT {
  int N; int max_2beki;

  vector< T > data;
  // 初期化 1-indexedでデータを管理する 0で初期化
  BIT(int size){
      N = ++size;
      data.assign(N, 0);
      max_2beki = 1;
      while(max_2beki * 2 <= N) max_2beki *= 2;
  }

  // [0,k](閉区間)の総和 閉区間に注意！
  T sum(int k) {
    if(k < 0) return 0; // k<0のとき0を返す
    T ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }

  // [l,r](閉区間)の総和
  inline T sum(int l,int r){
    return sum(r) - sum(l-1);
  }

  // 一点取得 更新はできないことに注意
  inline T operator[](int k){
    return sum(k) - sum(k-1);
  }

  // data[k] += x;
  void add(int k, T x) {
    for(++k; k < N; k += k & -k) data[k] += x;
  }

  // imos法 [l,r]にxを加算
  void imos(int l,int r,T x){
    add(l , x); add(r + 1 , -x);
  }

  // lower_bound sum(i)がval以上となる最小のi
  int lower_bound(T w){
    if(w <= 0) return 0;
    int x = 0;
    for(int k = max_2beki; k > 0; k /= 2){
      if(x+k <= N - 1 && data[x + k] < w){
        w -= data[x + k];
        x += k;
      }
    }
    return x;
  }

  // upper_bound sum(i)がvalより大きくなる最小のi
  int upper_bound(T w){
    if(w < 0) return 0;
    int x = 0;
    for(int k = max_2beki; k > 0; k /= 2){
      if(x+k <= N - 1 && data[x + k] <= w){
        w -= data[x + k];
        x += k;
      }
    }
    return x;
  }

};

void solve(){
  ins(T,S);ini(K);
  int N = sz(S) , M = sz(T);
  int offset = N + 1;
  S += "&";
  S += T;
  SuffixArray sa(S);
  LCPArray lcp(sa);
  //lcp.output();
  StringSearch search(lcp);
  vi left(sz(S) + 1, -1) , right(sz(S) + 1 , -1);
  {
    int cur = -1;
    rep(i,sz(S) + 1){
      left[i] = cur;
      if(sa.sa[i] <= N) cur = i;
    }
  }
  trc(left);
  {
    int cur = -1;
    repr(i,sz(S) + 1){
      right[i] = cur;
      if(sa.sa[i] <= N) cur = i;
    }
  }
  trc(right);
  BIT<int> bit(M + 3);
  vvi g(M + 1);
  for(int i=N+1;i<sz(S);i++){
    trc(left[lcp.rank[i]] , lcp.rank[i] , right[lcp.rank[i]]);
    int len = max(
      (left[lcp.rank[i]]!=-1? 
        search.ArbitaryLCP(sa.sa[left[lcp.rank[i]]],i): 0) ,
      (right[lcp.rank[i]]!=-1? 
        search.ArbitaryLCP(i,sa.sa[right[lcp.rank[i]]]): 0)
    );
    trc(len);
    if(len >= K){
      trc(i + K , i + len - 1);
      g[i-offset].pb(i-offset+K);
      if(K<=len-1) bit.imos( i-offset + K , i-offset + len - 1 , 1);
    }
  }
  rep(i,M){
    if(bit.sum(i)) g[i].pb(i + 1);
  }
  each(x,g) trc(x);
  vi ans(sz(T) + 1 , 0); ans[0] = 1;
  rep(i,sz(T)){
    if(ans[i] == 0) continue;
    each(x , g[i]) ans[x] = 1;
  }
  trc(ans);
  out(ans[sz(T)] ? "Yes" : "No");

}