洛谷P1026 统计单词个数

洛谷P1026 统计单词个数

题意：

给一个字符串（题目中是以20个字符为一组输入的），字符串被分为k段，然后给定几个“单词”，问各段包含的单词总数最多是多少？（emmm，我jio得我应该说清楚了，看不明白的话还是点击上方链接看原题吧…）

分析：

需要进行字符串匹配，所以很容易想到哈希
此处推荐一篇字符串哈希的博文：https://blog.csdn.net/pengwill97/article/details/80879387
枚举原始字符串的各个子串，与各个单词比较
用一个cnt数组记录各个子串中包含单词的数目
然后就是dp了
dp[i][j]表示前i个字符被划分为j段时包含的单词数的最大值
状态转移方程如下：
$dp\left[i\right]\left[j\right]=max\left(dp\right[i\left]\right[j],dp[v\left]\right[j-1]+cnt[v+1\left]\right[i\left]\right)$dp[i][j]=max(dp[i][j],dp[v][j−1]+cnt[v+1][i])
$0\&lt;=v\&lt;i$0<=v<i
$cnt[v+1]\left[i\right]$cnt[v+1][i]表示在区间[v+1,i]上包含的单词数

代码君：

#include <bits/stdc++.h>
using namespace std;
const int mod = 1610612741;
const int p = 769;
const int maxlen = 250;
string str, ss[11], word[10];
int ha[10], len[10];
int n, k, s;
int cnt[maxlen][maxlen] = {0}, dp[maxlen][maxlen] = {0};
int Hash(string &c)
{
    int len = c.length();
    int num = 1;
    for (int i = 0; i < len; ++i)
        num = (num * p + c[i]) % mod;
    return num;
}
bool judge(int x, int y)
{
    for (int i = 0; i < s; ++i)
    {
        string temp;
        temp = str.substr(x, min(len[i], y - x + 1));
        if (Hash(temp) == ha[i])
            return true;
    }
    return false;
}
int main(int argc, char const *argv[])
{
    // freopen("output2.txt", "w", stdout);
    cin >> n >> k;
    str = "";
    for (int i = 0; i < n; ++i)
    {
        cin >> ss[i];
        str += ss[i];
    }
    cin >> s;
    for (int i = 0; i < s; ++i)
        cin >> word[i], len[i] = word[i].length();
    for (int i = 0; i < s; ++i)
        ha[i] = Hash(word[i]);

    for (int i = str.length() - 1; i >= 0; --i)
    {
        for (int j = i; j >= 0; --j) //因为题目中说“每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用”，所以只能倒着枚举
        {
            cnt[j][i] = cnt[j + 1][i];
            if (judge(j, i))
                cnt[j][i]++;
        }
    }

    for (int i = 0; i < str.length(); ++i)
    {
        for (int j = 1; j <= k; ++j)
        {
            if (j == 1)
                dp[i][j] = cnt[0][i];
            else
            {
                for (int v = 0; v < i; ++v)
                {
                    if (v >= j - 1) //这个判断很重要！！！自己思考为什么
                        dp[i][j] = max(dp[i][j], dp[v][j - 1] + cnt[v + 1][i]);
                }
            }
        }
    }
    cout << dp[str.length() - 1][k] << endl;
    return 0;
}