USACO chapter 2 section 2.3 The Longest Prefix
7636 ワード
USACO chapter 2 section 2.3 The Longest Prefix
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
;
}