USER: tian tianbing [tbbd4261]
TASK: prefix
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 6916 KB]
Test 2: TEST OK [0.000 secs, 6916 KB]
Test 3: TEST OK [0.000 secs, 6916 KB]
Test 4: TEST OK [0.000 secs, 6916 KB]
Test 5: TEST OK [0.022 secs, 6916 KB]
Test 6: TEST OK [0.173 secs, 6916 KB]
All tests OK.
Your program ('prefix') produced all correct answers! This is your
submission #5 for this problem. Congratulations!
DP:dp[i]=(dp[i]||dp[i-ll]);
dp[i]表示前缀可到达的长度为i。如果对于所有dp[i-ll]均为假则dp[i]不可能为真。
/*
ID:tbbd4261
PROG:prefix
LANG:C++
*/
#include<iostream>
#include<fstream>
#include<string>
#include<cstring>
using namespace std;
ifstream fin("prefix.in");
ofstream fout("prefix.out");
const int MAX=2000005;
string prefix[205];
char s[MAX]={0};
bool dp[MAX]={0};
int cnt=0,n=0,i=0,j=0,k;
int main()
{
while(fin>>prefix[++cnt], prefix[cnt]!=".")
;
cnt--;
char ch; i=0;
while(fin>>ch)s[++i]=ch;
n=i;
bool flag;
dp[0]=true;
for( i=1; i<=n; i++)
{
for(j=1; j<=cnt; j++)
{
flag=true;
int ll=prefix[j].length();
if(i<ll)continue;
for(k=0; k<ll; k++)
if(prefix[j][k]!=s[i-ll+1+k])
{
flag=false; break;
}
if(flag)dp[i]=(dp[i]||dp[i-ll]);
if(dp[i])break;
}
}
for(k=n; k>=0; k--)
if(dp[k]) { fout<<k<<endl; break;}
return 0;
}