scanf("%s", &word);
for(int i = 0; i < N; ++i)
{
scanf("%s", &s[i]);
len[i] = strlen(s[i]);
}
v[0] = 1;
for(int i = 0; i < N; ++i)
if(len[i] == 1 && word[0] == s[i][0])
v[0] = 0;
for(int i = 1; i < L; ++i)
{
int Min = v[i-1]+1;
for(int j = 0; j < N; ++j)
if(i+1 >= len[j] && s[j][len[j]-1] == word[i])
{
int index = i-1;
int pos = len[j]-2;
while(index >= 0 && pos >= 0)
{
if(s[j][pos] == word[index])
pos--;
index--;
}
if(pos < 0 && v[index] + i-index-len[j] < Min)
Min = v[index] + i-index-len[j];
}
v[i] = Min;
}
printf("%d/n", v[L-1]);
return 0;
}
/*
//Learned:
本题若从后往前按照每个单词进行匹配,效率会高很多很多.
下面的TLE的解法就是因为对每个num[k+1, i]进行每个单词的匹配,效率很低.
YJS:
for(int j = 0; j < N; ++j)
vs
for(int k = 0; k < i; ++k) && for(int i = 0; i < N; ++i)
状态转移方程为: v[i] = min{v[k], num[k+1, i]}
Problem: 3267 User: xiaofengsheng
Memory: 412K Time: 63MS
Language: G++ Result: Accepted
*/
/*#include <iostream>
#include <string>
using namespace std;
int v[302];
char s[600][27];
char word[302];
int len[600];
int N, L;
//v[i] = min{v[k], num[k+1, i]} (-1 <= k <= i-1);
inline int f(int m, int n)
{
int Min = 100000;
bool flag = false;
for(int i = 0; i < N; ++i)
{
int pos = 0;
int index = m;
while(index <= n && pos < len[i])
{
if(s[i][pos] == word[index])
pos++;
index++;
}
if(pos == len[i] && n-m+1-pos < Min)
{
Min =n-m+1-pos;
flag = true;
}
}
if(flag)
return Min;
else
return n-m+1;
}
int main()
{
scanf("%d%d", &N, &L);
scanf("%s", &word);
for(int i = 0; i < N; ++i)
{
scanf("%s", &s[i]);
len[i] = strlen(s[i]);
}
for(int i = 0; i < N; ++i)
puts(s[i]);
v[0] = 1;
for(int i = 0; i < N; ++i)
if(len[i] == 1 && word[0] == s[i][0])
v[0] = 0;
for(int i = 1; i < L; ++i)
{
int Min = f(0, i);
for(int k = 0; k < i; ++k)
{
int ret = f(k+1, i);
if(v[k] + ret < Min)
Min = v[k] + ret;
}
v[i] = Min;
}
printf("%d/n", v[L-1]);
return 0;
}
*/