47 条题解
-
0
chen199277 LV 10 @ 2009-10-29 20:15:57
Orz..ckl8520
-
0
181818181818 LV 10 @ 2009-10-29 15:38:20
楼下的楼下的楼下能给个证明吗？
感觉有点奇怪，为什么是对的呢？ -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms牛X的KMP！43..........
-
0
prince_hao LV 10 @ 2009-10-27 21:20:58
哎~~~
这种东西的正确性好搞脑子
不过在楼下各位牛的强力引导下还是1A了！ -
0
1314lovehh LV 8 @ 2009-10-27 19:35:10
膜拜神牛们啊
-
0
跪求数据 这个题目纯模拟 10分 编了另一个方法 仍旧10分 而且但答案跟纯模拟一样 请大牛给点数据 帮我改下 QQ373627964 邮箱 373627964@qq.com
-
0
mingyuangao LV 6 @ 2009-10-26 22:07:26
谁给我解释一下！！这个东西为什么not compiled！！！！
Program test2;
var
n,l,num:longint;
str,str1:ansistring;
con:array[0..255] of boolean;procedure init;
var
i:longint;
begin
readln(str);
writeln(str);
n:=length(str);
fillchar(con,sizeof(con),false);
for i:=1 to n do
if con[ord(str[i])]=false
then
begin
inc(num);
con[ord(str[i])]:=true;
end;
end;function check(k:longint;str1:ansistring):boolean;
var
i:longint;
begin
if k=n-l
then
exit(true);
for i:=1 to l do
if (str[k+i]str1[i]) and (str[k+i]str1[1])
then
exit(false)
else
if (str[k+i]=str[1]) and (i1)
then
check:=check(k+i-1,str1);
end;function contain(str1:ansistring):boolean;
var
i:longint;
begin
for i:=0 to 255 do
if (con[i]) and (pos(chr(i),str1)=0)
then
exit(false);
contain:=true;
end;procedure paint;
var
i:longint;
begin
for l:=num to n do
begin
str1:=copy(str,1,l);
if (str1=copy(str,n-l+1,l)) and contain(str1)
then
if (l=n) or (check(l,copy(str,1,l)))
then
begin
writeln(l);
exit;
end;
end;
end;Begin
init;
paint;
End. -
0
zjy19951109 LV 8 @ 2009-10-26 18:25:44
这题目太过分了。。。。。。。
-
0
直接KMP，计算每个字符的自匹配，用p[i]表示第i个
的自匹配位置
设T为最大的i，其中p[i]=0，
然后记长度为len，开始时ans:=len；
按他的自匹配向前推，直到ans=i；p[i]=T;ans=T;ans-
人依然俊秀 @ 2013-11-06 09:35:02
大神请留步~~
-
12100 @ 2014-07-19 11:07:04
敢问 大神那个 T是 什么意思
-
坑.
-
1756500824 @ 2014-07-26 19:56:49
能不能请你发一下代码
-
ALXPCUN @ 2015-05-19 15:04:51
ababacabac呢？
-
zls6602488 @ 2016-01-28 16:22:01
ababc就出问题了。。。
-
是我错了，大神佩服，orz。。。
-
-
0
首先考虑下答案性质，设答案为前缀I，复制的时候相邻两个位置设为(k,q)则s[K~Q]必定等于s[1~q-k+1].并且s[len-i+1]必定等于s[1~i].
考虑到一个前缀i能成为答案当且仅当存在若干个点，其中最末尾的点在n+1,且相邻点(k,q)满足[K~Q]必定等于s[1~q-k+1]，且q-k+1=I即可，因为除了now+1-i这个点，1~now都不可能更新最远距离，如果是，则维护一个指针now'=now+1，然后now不断往右移动，再判定lcp[now]+now是否>now'，是则更新。这样不断维护now'和now的值直到now=now'即可。
hint:LCP是每个点与前缀的最大匹配，题解所说的二分长度实际上就是指，上文中最小的前缀满足最远距离=n+1
chen199277
LV 10
@ 2009-10-29 20:15:57
