京东CPP开发方向编程题题解

#include <bits/stdc++.h>
using namespace std;

const long long mod = 1e9 + 7;
int len[10];
char S[10][100005];
char T[100005];
int state[100005];
int dp[100005];
long long hsh[100005];
long long mi[100005];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%s", S[i]), len[i] = strlen(S[i]);
    scanf("%s", T);
    mi[0] = 1;
    for (int i = 1; i <= 100000; i++)
        mi[i] = mi[i - 1] * 31 % mod;
    int lenT = strlen(T);
    hsh[0] = T[0] - 'a' + 1;
    for (int i = 1; i < lenT; i++)
        hsh[i] = (hsh[i - 1] * 31 + T[i] - 'a' + 1) % mod;
    for (int i = 0; i < n; i++)
    {
        long long curHsh = 0;
        for (int j = 0; j < len[i]; j++)
            curHsh = (curHsh * 31 + S[i][j] - 'a' + 1) % mod;
        if (curHsh == hsh[len[i]-1])
            state[len[i]-1] |= 1 << i;
        for (int j = len[i]; j < lenT; j++)
            if ((hsh[j] - hsh[j - len[i]] * mi[len[i]] % mod + mod) % mod == curHsh)
                state[j] |= 1 << i;
    }
    for (int i = 0; i < lenT; i++)
    {
        int minL = 1e9;
        for (int j = 0; j < n; j++)
            if (state[i] & (1 << j))
                minL = min(minL, len[j]);
        if (minL == 1e9)
        {
            if (i > 0)
                dp[i] = dp[i-1];
        }
        else if (i-minL < 0)
            dp[i] = max(dp[i-1], 1);
        else
            dp[i] = max(dp[i-1], dp[i-minL]+1);
    }
    printf("%d", dp[lenT - 1]);
    return 0;
}