洛谷题单指南-字符串-P1470 [USACO2.3] 最长前缀 Longest Prefix

原题链接：https://www.luogu.com.cn/problem/P1470

题意解读：求s最长前缀长度，使得可以拆解成p集合中的字符串

解题思路：

动态规划：

设s字符串下标从1开始，p集合用set<string>保存所有的元素

状态表示：设f[i]表示前i个字符s[0~i-1]是否能拆解成p中的元素

状态计算：对于j = i - 1开始往后倒推最多10个，如果f[j] = true并且j+1~i之间子串在p中，说明f[i] = true

初始化：f[0] = true

结果：最大的i

100分代码：

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

const int N = 200005;
set<string> p;
string s;
bool f[N]; //f[i]表示前i个字符s[0~i-1]是否能拆解成p中的元素
int ans;

int main()
{
    string tmp;
    bool first = true;
    while(cin >> tmp)
    {
        if(tmp == ".") first = false;
        else
        {
            if(first) p.insert(tmp);
            else s += tmp;
        }
    }
    s = " " + s; //s从1开始，比正常长度增加了1
    f[0] = true;
    for(int i = 1; i < s.size(); i++)
    {
        for(int j = i - 1; j >= 0 && j >= i - 10; j--) //j从i-1往回最多退10个长度
        {
            string ss = s.substr(j + 1, i - j); //提取j+1~i之间的子串
            if(f[j] && p.count(ss) > 0) //如果f[j]为true且j+1~i之间子串在p中，说明前i个字符也符合要求
            {
                f[i] = true;
                ans = max(ans, i);
            }
        }
    }
    cout << ans;
    return 0;
}