Python3(3.9) 解法, 执行用时: 558ms, 内存消耗: 4756K, 提交时间: 2022-04-04 22:31:26

d = {}
def search(sentence): 
    if sentence == '': return 0
    if sentence in d: return d[sentence]
    ans = len(sentence)
    for word in words:
        pos = 0
        pos_word = 0
        while pos < len(sentence):
            if sentence[pos] == word[pos_word]:
                pos_word += 1
                if pos_word == len(word): break
            pos += 1
        if pos_word == len(word):
            ans = min(ans, pos+1-len(word)+search(sentence[pos+1:]))
    d[sentence] = ans
    return ans

w, l = [int(x) for x in input().split()]
sentence = input()
words = set()
for _ in range(w):
    words.add(input())
print(search(sentence))

C++(g++ 7.5.0)(g++7.5.0) 解法, 执行用时: 90ms, 内存消耗: 384K, 提交时间: 2023-08-08 16:21:30

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char str[605][30], jud[305];
int dp[305];
int main(void)
{
	int n, m, i, j, p, q, sum;
	scanf("%d%d", &n, &m);
	scanf("%s", jud+1);
	for(i=1;i<=n;i++)
		scanf("%s", str[i]+1);
	for(i=0;i<=m;i++)
		dp[i] = i;
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
			sum = 0;
			p = i, q = strlen(str[j]+1);
			while(p>=1 && q>=1)
			{
				if(jud[p]==str[j][q])
					q--, sum++;
				p--;
			}
			if(q==0)
				dp[i] = min(dp[i], dp[p]+(i-p-(int)strlen(str[j]+1)));
		}
	}
	printf("%d\n", dp[m]);
	return 0;
}

C++(clang++11) 解法, 执行用时: 69ms, 内存消耗: 432K, 提交时间: 2022-04-13 16:55:46

#include<bits/stdc++.h>
using namespace std;
int n,m,f[1005];
char a[1005];
string s[1005];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	    cin>>a[i];
	for(int i=1;i<=n;i++) 
	    cin>>s[i];
	for(int i=1;i<=m;i++)
    {
		f[i]=f[i-1]+1;
	    for(int j=1;j<=n;j++)
	  	{
	  		int l=s[j].length()-1,l1=i;
	  		while(l>=0&&l1>=1)
            {
	  		    l-=(s[j][l]==a[l1]);
                l1--;
			}
			if(l==-1)
                f[i]=min(f[i],f[l1]+i-l1-int(s[j].length()));
		}
	}
	cout<<f[m];
	return 0;
}