问题 3914 --可拼接得到的最长前缀(完善程序)

3914: 可拼接得到的最长前缀(完善程序)★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 105  解决: 86
[提交][状态][命题人:]

题目描述

给定一个单词集合,每个单词间以空格隔开,用.表示单词集合结束,接下来给出一个字符串,求字符串的最长前缀使得该前缀能够由给定的单词集合拼接而成,输出一个整数,表示符合条件的前缀的最大长度
下列程序用dp的方式完成了这个任务,请完善程序
#include <bits/stdc++.h>
using namespace std;
int main() 
{
   vector<string> prefix;
    string p,str;
    while (true) 
	{
        cin >> p;
        if (_____(1)______) break;
        prefix.push_back(p);
    }
    cin >> str;
    int len = (int)str.length();
    vector<bool> dp(len + 1, false);
    ______(2)_______;
    for (int i = 0; i < len; i++) 
	{
        if (dp[i]) 
		{
            for (int j = 0; j < prefix.size(); j++) 
			{
                bool isMatched = true;
                for (int k = 0; k < prefix[j].length(); k++) 
				{
                    if (______(3)______)
					{
                        isMatched = false;
                        break;
                    }
                }
                if (isMatched) dp[______(4)______] = true;
            }
        }
    }
    for (int i = len; i >= 0; i--) 
	{
        if (____(5)______)
		{
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}

输入

输出

样例输入
Copy
zhe jiang sheng shao xing shi xin chang xian .
xingjiang
样例输出
Copy
9

提示

来源

[提交][状态]