题意：给出一个字符串t，现在可以在这个字符串后面加n个k以下的字母，询问一种方案，使得加了n个字母后的字符串中不相同的子串（子串不一定连续）最多。
思路：首先先看给定的字符串t，要解决的第一个问题是要如何求字符串t中不相同的子串数量。
这一步可以dp来做，用dp[i]表示位置i之前的子串数量，假设当前已经考虑到了第i个位置，也就是说之前的dp[0]~dp[i-1]已经求了出来，
再用pos[j]表示字符j上次出现的位置
对于当前位置i来说，因为比上一次多了一个字符，所以会增加dp[I-1]个以当前字符结尾的新子串，但是这些子串中有重复的，也就是以当前字符上次位置作为结束位置的子串数量。
所以可以得到转移方程dp[I] = dp[I-1] * 2 - dp[ pos[t[I] - 1] ];
剩下的问题就是向这个字符串后面加字符串了，怎么加才能使最后的字符串子串数量最多呢，方法是每加一个位置都取当前的最优解，也就是局部的最优解就是整体的最优解
可以贪心的来想，考虑字符串后的第一个位置，肯定是加之前所有pos[j]中最小的，然后就确定了这一步的位置，然后每一步都这样取最优解
但这样是否能保证最后的解一定是最优解呢？答案是肯定的，因为根据上面的转移方程其实最后的子串数量等于
(dp[len]<<n) - (pos1<<(n-1)) - (pos2<<(n-2)) - ......posn （posk为第k个位置选取的位置）
可以看到每一项的权值都大于后面的所有项的和，所以局部最优可以保证全局最优。
#include<bits/stdc++.h>
#define eps 1e-6
#define LL long long
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int MAXN = 1000100;
const int MOD = 1e9+7;
int n, k;
LL dp[MAXN];
int pos[30];
char t[MAXN];
int main()
{
freopen("input.txt", "r", stdin);
scanf("%d%d%s", &n, &k, t+1);
int len = strlen(t+1);
dp[0] = 1;
for (int i = 1; i <= len; i++) {
dp[i] = (dp[i-1]<<1);
if (pos[t[i]-'a'] > 0)
dp[i] -= dp[pos[t[i]-'a']-1];
dp[i] %= MOD;
pos[t[i]-'a'] = i;
}
for (int i = len+1; i <= len+n; i++) {
dp[i] = (dp[i-1]<<1);
int id, p = i;
for (int j = 0; j < k; j++) {
if (pos[j] < p) {
p = pos[j];
id = j;
}
}
if (p > 0)
dp[i] -= dp[p-1];
dp[i] %= MOD;
pos[id] = i;
}
printf("%d", (dp[len+n]+MOD)%MOD);
return 0;
}