C++ 解法, 执行用时: 20ms, 内存消耗: 13432KB, 提交时间: 2020-12-22

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
  
  
using namespace std;
  
const int N = 110000;
const int M = 10;
  
struct Mp
{
    int len, id;
}mp[M];
bool cmp(Mp a, Mp b)
{
    return a.len<b.len;
}
  
char sn[M][N];
char ss[N];
  
int nextt[M][N];
int match[M][N];
  
void kmp(int n)
{
    int i, j, k;
    int sslen = strlen(ss + 1);
    for (i = 0; i<n; i++)
    {
        nextt[i][1] = 0;
        for (j = 2; j <= mp[i].len; j++)
        {
            int t = nextt[i][j - 1];
            while (t&&sn[i][t + 1] != sn[i][j]) t = nextt[i][t];
            if (sn[i][t + 1] == sn[i][j]) nextt[i][j] = t + 1;
            else nextt[i][j] = 0;
        }
        match[i][0] = 0;
        for (j = 1; j <= sslen; j++)
        {
            int t = match[i][j - 1];
            while (t&&sn[i][t + 1] != ss[j]) t = nextt[i][t];
            if (sn[i][t + 1] == ss[j]) match[i][j] = t + 1;
            else match[i][j] = 0;
            //cout<<match[i][j];
        }
        //cout<<endl;
    }
}
  
int dp[N];
int dfs(int l, int n)
{
    if (l == 0) return 0;
    if (dp[l] != -1) return dp[l];
    int i, j, k;
    int ret = 0;
    for (i = 0; i<n; i++)
    {
        int len = mp[i].len;
        if (match[i][l] == len)
        {
            ret = max(ret, dfs(l - len, n) + 1);
        }
    }
    ret = max(ret, dfs(l - 1, n));
    dp[l] = ret;
    return ret;
}
  
  
  
int main()
{
    int i, j, k, n;
    cin >> n;
    for (i = 0; i<n; i++)
    {
        scanf("%s", sn[i] + 1);
        mp[i].len = strlen(sn[i] + 1), mp[i].id = i;
    }
    scanf("%s", ss + 1);
    kmp(n);
    //sort(mp,mp+n);
    int sslen = strlen(ss + 1);
    memset(dp, -1, sizeof(dp));
    dfs(sslen, n);
    cout << dp[sslen] << endl;
    return 0;
}

C++ 解法, 执行用时: 21ms, 内存消耗: 1804KB, 提交时间: 2020-09-17

/*
author Owen_Q
*/
 
#include<bits/stdc++.h>
 
using namespace std;
 
const int maxn = 1e2+7;
 
string s[maxn];
int a[maxn];
 
int main()
{
    int m;
    cin >> m;
    for(int i=0;i<m;i++)
    {
        cin >> s[i];
        a[i] = s[i].size();
    }
    string t;
    cin >> t;
    int n = t.size();
    int now = 0;
    int pos = 0;
    int re = 0;
    while(now<n)
    {
        for(int i=0;i<m;i++)
        {
            if(pos+a[i]-1<=now)
            {
                int tmp = 0;
                while(tmp<a[i])
                {
                    //cout << s[a[i]-1-tmp] <<"*" << t[now-tmp] << endl;
                    if(s[i][a[i]-1-tmp]!=t[now-tmp])
                        break;
                    tmp++;
                }
                if(tmp == a[i])
                {
                    re++;
                    //cout << now << "*" << i << endl;
                    pos = now+1;
                    break;
                }
            }
        }
       now++;
    }
    cout << re << endl;
    return 0;
}
/*
注意每次改局部代码对整体代码的影响
*/