思想

字符串哈希，然后用ml[i]存储字符串s中匹配字符串t中1～i的字符串的最后一个字符的坐标，mr[i]存储字符串s中匹配字符串t中i～m的字符串的第一个字符的坐标。最后遍历1～m开始是否能凑出包含t的两个字符串。

代码

import java.io.*;

public class Main{
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    static int N = 10010, n, m, k;
    static long P = 131, Q = Long.MAX_VALUE;
    static long[] p = new long[N];
    static long[] h1 = new long[N];
    static long[] h2 = new long[N];
    static int[] ml = new int[N];           //ml[i]存储的是字符串s中匹配字符串t中1～i的字符串的最后一个字符的坐标
    static int[] mr = new int[N];           //mr[i]存储的是字符串s中匹配字符串t中i～m的字符串的第一个字符的坐标

    public static long get1(int l, int r){
        return h1[r]-h1[l-1]*p[r-l+1];
    }

    public static long get2(int l, int r){
        return h2[r]-h2[l-1]*p[r-l+1];
    }

    public static void main(String[] args)throws IOException{
        String[] input = in.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        k = Integer.parseInt(input[2]);

        String s = " "+in.readLine(), t = " "+in.readLine();
        char[] c1 = s.toCharArray();
        char[] c2 = t.toCharArray();
        //计算字符串哈希
        p[0] = 1;
        for(int i=1; i<=n; i++) p[i] = p[i-1]*P%Q;
        for(int i=1; i<=n; i++) h1[i] = (h1[i-1]*P%Q+c1[i])%Q;
        for(int i=1; i<=m; i++) h2[i] = (h2[i-1]*P%Q+c2[i])%Q;

        //开始计算ml[]和mr[]
        int pos = k;        //pos从k开始往后移动以确保最后得到的匹配前缀可以扩充到长度k
        //遍历可以取到的所有长度
        for(int i=1; i<=Math.min(m, k); i++){
            while(pos<=n && get1(pos-i+1, pos)!=get2(1, i)) pos++;
            ml[i] = pos;
        }
        pos = n-k+1;
        //遍历可以取到的所有长度,!!!这里要注意mr[]的下标要和get2(m-i+1, m)的起始下标统一
        for(int i=1; i<=Math.min(m, k); i++){
            while(pos>=1 && get1(pos, pos+i-1)!=get2(m-i+1, m)) pos--;
            mr[m-i+1] = pos;
        }
        for(int i=1; i<=m; i++){
            //确保不相交
            if(ml[i]<mr[i+1] && ml[i]<=n && mr[i+1]>=1){
                out.println("Yes");
                out.flush();
                out.close();
                return;
            }
        }
        out.println("No");
        out.flush();
        out.close();
        return;
    }
}