Cod sursă (job #735724)

#include <bits/stdc++.h>
using namespace std;
const int KMAX = 1e4;
const int NMAX = 1e4+2;
const int SIGMA = 26;
int n,k,dp[KMAX][NMAX],lst[KMAX][SIGMA];
string str;

ifstream fin("director.in");
ofstream fout("director.out");

int main()
{
    fin >> n >> k;
    fin >> str;
    str = "$"+str;
    dp[0][0] = 1;
    memset(lst, -1, sizeof(lst));
    for(int i = 1; i <= n; i++){
        int ch = str[i]-'a';
        dp[0][i] = 1;
        for(int len = 1; len <= k && len <= i; len++){
            dp[len][i] = dp[len][i-1] + (dp[len-1][i-1] - (lst[len-1][ch] != -1 ? dp[len-1][lst[len-1][ch]] : 0));
        }
        for(int len = 0; len <= k && len <= i; len++){
            lst[len][ch] = i-1;
        }
    }
    fout << dp[k][n];
    return 0;
}