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 <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define mod 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
class suffixarray{
public:
    int sz,index1,index2;
    vector<int> rnk,tmp,sa,lcp;
    string recs;
    suffixarray(string s){
        recs = s;
        sz = (int)s.size();
        rnk.resize(sz+1),tmp.resize(sz+1);
        make_sa();
        make_lcp();
    }
    void make_sa(){
        index1 = sz;
        sa.resize(index1+1);
        for(int i = 0; i < index1+1; i++){
            sa[i] = i;
            rnk[i] = i<index1?recs[i]:-1;
        }
        auto comp = [&](int i,int j){
            if(rnk[i] != rnk[j]){
                return rnk[i] < rnk[j];
            }else{
                int ri = (i+index2<=index1)?rnk[i+index2]:-1;
                int rj = (j+index2<=index1)?rnk[j+index2]:-1;
                return ri < rj;
            }
        };
        for(index2=1;index2<=index1;index2*=2){
            sort(sa.begin(),sa.end(),comp);
            tmp[sa[0]] = 0;
            for(int i=1;i<=index1;i++){
                tmp[sa[i]] = tmp[sa[i-1]]+(comp(sa[i-1],sa[i])?1:0);
            }
            for(int i = 0; i < index1+1; i++){
                rnk[i] = tmp[i];
            }
        }
    }
    void make_lcp(){
        lcp.resize(sz+1);
        for(int i = 0; i < sz+1; i++){
            rnk[sa[i]] = i;
        }
        int h = 0;
        lcp[0] = 0;
        for(int i = 0; i < sz; i++){
            int j = sa[rnk[i]-1];
            if(h > 0){
                h--;
            }
            for(;j+h<sz&&i+h<sz;h++){
                if(recs[j+h] != recs[i+h]){
                    break;
                }
            }
            lcp[rnk[i]-1] = h;
        }
    }
};
int main(){
    string s,t;
    cin >> s >> t;
    int n = s.size();
    int m = t.size();
    int sz = s.size()+t.size()+1;
    string p = s + "~" + t;
    int a = s.size();
    int b = t.size();
    suffixarray SA(p);
    vector<int> sa = SA.sa;
    vector<int> lcp = SA.lcp;
    sz = sa.size();
    // rep(i,sz){
    //     cerr << sa[i] << " " << lcp[i] << endl;
    //     cerr << p[sa[i]] << endl;
    // }
    vector<int> flag(sz+100000);
    rep(i,sz){
        if(sa[i]>=a+1&&sa[i]<a+1+b){
            //cerr <<sa[i] << " " << p[sa[i]] << endl;
            flag[i] = true;
        }
    }
    vector<int> len(a+100000);
    int tmp = 0;
    rep(i,sz){
        if(flag[i]){
            tmp = lcp[i];
        }else{
            len[sa[i]] = max(len[sa[i]],tmp);
            tmp = min(tmp,lcp[i]);
        }
    }
    int k;
    cin >> k;
    
    tmp = 0;
    rep(i,sz){
        if(flag[sz-1-i]){
            if(sz-2-i<0)continue;
            tmp = lcp[sz-2-i];
        }else{
            len[sa[sz-1-i]] = max(len[sa[sz-1-i]],tmp);
            if(i!=sz-1)tmp = min(tmp,lcp[sz-2-i]);
        }
    }
    // rep(i,a){
    //     cout << len[i] << endl;
    // }
    
    // if(k!=4&&k!=1){
    //     cout << "WA" << endl;
    //     return 0;
    // }
    vector<int> dp(a+100000);
    dp[a] = 1;
    vector<int> dp2(a+300000);
    dp2[a] = 1;
    
    for(int i=sz-1;i>=0;i--){
        dp2[i] += dp2[i+1];
        
        if(len[i]<k)continue;
        
        if(len[i]>=k){
            if(dp2[i+k]-dp2[i+len[i]+1]>0){
                dp[i] = 1;
            }
            // for(int j=i+k;j<=i+len[i];j++){
            //     if(dp[j]){
            //         dp[i] = true;
            //         break;
            //     }
            // }
        }
        dp2[i] += dp[i];
    }
    if(dp[0]){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}