此题要找出能用所给集合表示出来的最长前缀,想法是与给出的元素挨个比较,只要找到与之相等的就可以了。
此题有点动态规划的味道,写博客时想到的状态转移方程,设dp[i]表示主串S中从i开始的最长的可组成的前缀,dp[1]就是所求,状态转移方程:
dp[i]=max{dp[j]+j-i}|i到j-1的字串是primitive。 i<j<=n。
下面的代码没用这个状态转移方程,但是思想跟这个差不多。
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
using namespace std;
string pre[201];
string s;
string temp;
int l[201],n=0,len,Max=0;
int main()
{
freopen("prefix.in","r",stdin);
freopen("prefix.out","w",stdout);
while(1)
{
cin>>pre[n];
l[n]=pre[n].size();
if(pre[n][0]=='.')
break;
n++;
}
while(cin>>temp)
s+=temp;
len=s.size();
for(int i=0;i<len;i++)
{
for(int j=0;j<n;j++)
{
bool flag=true;
if(i+l[j]>len)continue;
for(int k=0;k<l[j];k++)
if(s[i+k]!=pre[j][k])
{
flag=false;
break;
}
if(flag)
Max=Max>l[j]+i?Max:l[j]+i;
}
if(i+1>Max)//一点小优化
break;
}
cout<<Max<<endl;
return 0;
}