死嗑 字符串

最长前缀 Longest Prefix

#include <bits/stdc++.h> using namespace std; const int N=1e6+10; set<string> s; int dp[N]; int main() { string str; int len=1; while(cin>>str) { if(str==".") break; s.insert(str); int size=str.length(); len=max(len,size); } int ans=0; dp[0]=1; string n=" ",qwq; while(cin>>qwq) { n=n+qwq; //多行合并成一行 } for(int i=1;i<n.length();i++) //因为是前缀 ,所以 i 不用等于 n.length() { for(int j=min(i,len);j>=1;j--) //这个 min 用的妙啊 { string tt=n.substr(i-j+1,j); if(s.count(tt)&&dp[i-j]==1) { ans=i; dp[i]=1; break; //记得直接跳过 } } } cout<<ans; return 0; }

思路： DP + 字符串 ① 用 set 集合储存第一行的元素（并记录最长的元素的长度） ② dp 数组表示：dp[i] 即第 i 个之前的字符串都是合法的前缀（可用元素表示的） ③ 之所以要用在接收的字符串前加个空格是为了从 i = 1 开始计数，ans = i 即最大的前缀长度（答案是包括 1 的） ④ 具体算法如下（以 ababc 举例）：

a ab abc 元素 _ababc 加了空格的字符串 循环实现方法如下 : _ababc a i = 1 ab i = 2 b i = 2 abc i = 3 bc i = 3 c i = 3 bab i = 4 ab i = 4 b i = 4 abc i = 5 bc i = 5 c i = 5