子串

import java.util.;
import java.io.;

class Main {
public static int N = 1010, M = 210, P = 1000000007;
public static int[][][][] dp = new int[2][M][M][2]; // 使用滚动数组优化
public static Scanner sc = new Scanner(System.in);

public static void main(String[] args) {
    int n = sc.nextInt(), m = sc.nextInt(), K = sc.nextInt();
    String s = sc.next(), t = sc.next();

    for (int i = 0; i <= n; i++) dp[i % 2][0][0][0] = 1; // 初始化优化
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 1; k <= K; k++) {
                dp[i % 2][j][k][0] = 0; // 重置当前状态
                dp[i % 2][j][k][1] = 0; // 重置当前状态
                if (s.charAt(i - 1) == t.charAt(j - 1))
                    dp[i % 2][j][k][1] = (int)(((long)dp[(i - 1) % 2][j - 1][k][1] + dp[(i - 1) % 2][j - 1][k - 1][0] + dp[(i - 1) % 2][j - 1][k - 1][1]) % P);
                dp[i % 2][j][k][0] = (int)(((long)dp[(i - 1) % 2][j][k][1] + dp[(i - 1) % 2][j][k][0]) % P);
            }

    System.out.println((int)(((long)dp[n % 2][m][K][1] + dp[n % 2][m][K][0]) % P));
}

}