68 条题解
-
0
我是天才他哥 LV 10 @ 2009-07-15 18:31:46
没有用KMP,堆栈也可以0MS过...
另外问问第六个点，怎么办
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
├ 测试数据 11：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms这题目用kmp真是大材小用，直接O（n）判断两个串是否相同就行了
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
├ 测试数据 11：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms这道题是KMP算法的一个扩展。
首先，将A串做一个自匹配，计算每一位的pre[i]值。
然后在匹配时将结果记录在一个栈里，记录B串每个元素能匹配的最大长度，然后如果某个元素能匹配整个A串，就将栈顶的length(A)个元素弹出，答案值加一。最后结果就是答案。注意：
1 有可能是前面的某一段在匹配断开以后，由于后面的一段的删除而重新得到匹配，比如：
A='abc'
B='ababcc'
B串为'ab'+'abc'+'c'
在中间的'abc'被删除后，第一段'ab'与第三段'c'又因为匹配而倍删除，因此这不是传统的KMP问题，而是要用一个栈来记录。
2 当匹配断掉时，该元素也要进栈，这是一个阻隔，防止出现不合理的情况。然而数据很弱，只有一个点卡这个情况。
3 数组要开到足够大，我将B串长度开到100000就216，开到1000000就AC了！ -
0
ufo172849z LV 10 @ 2009-02-28 22:03:12
栈加KMP，AC。
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 25ms
├ 测试数据 11：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：25ms数组怕爆开大了，成绩有点难看。
-
0
181818181818 LV 10 @ 2008-12-24 18:41:47
不用kmp
-
0
w122185976 LV 10 @ 2008-12-24 17:56:15
呃,500KB是个什么概念啊?
天啊!├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 853ms
├ 测试数据 04：运行超时...
├ 测试数据 05：运行超时...
├ 测试数据 06：运行超时...
├ 测试数据 07：运行超时...
├ 测试数据 08：运行超时...
├ 测试数据 09：运行超时...
├ 测试数据 10：运行超时...
├ 测试数据 11：运行超时... -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
├ 测试数据 11：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms你可以在这里写上你的解题思路或者解题方法等
但规定要求不能贴出任何有关于此题的程序代码 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
├ 测试数据 11：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms假!骗人的吧!用栈也可以秒杀的啊
-
0
Unaccepted 有效得分：60 有效耗时：1159ms
第一遍，朴素模拟。
---|---|---|---|---|---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：0 有效耗时：0ms
第二遍，改成栈之后挂掉。
---|---|---|---|---|---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：20 有效耗时：0ms
终于不超时了，但只有20分
---|---|---|---|---|---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
coLor_fish9 LV 10 @ 2008-10-28 15:37:33
晕死啊第六组数组到底怎么过......用栈做的
-
0
-
0
ljj5112898 LV 3 @ 2008-09-29 21:22:23
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
├ 测试数据 11：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msMMD,交了N^N次才过,整个程序都改掉了...
栈——>链表...
终于很囧的过了 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：运行超时...
├ 测试数据 04：运行超时...
├ 测试数据 05：运行超时...
├ 测试数据 06：运行超时...
├ 测试数据 07：运行超时...
├ 测试数据 08：运行超时...
├ 测试数据 09：运行超时...
├ 测试数据 10：运行超时...
├ 测试数据 11：运行超时...
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：20 有效耗时：0ms
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
├ 测试数据 11：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
这就是朴素模拟和KMP+栈的区别...
你可以在这里写上你的解题思路或者解题方法等但规定要求不能贴出任何有关于此题的程序代码
我是天才他哥
LV 10
@ 2009-07-15 18:31:46
