栈

编译通过...

├ 测试数据 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

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 41ms

├ 测试数据 11：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：50ms

KMP+栈处理

昨天用模拟做，结果后8组全部超时，

今天用栈做也全过，呵呵！

看来只要多去想一些问题就会很有收获的！

以此题为开始，冲刺noip2008，

决战2009年高考！！！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 134ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 291ms

├ 测试数据 09：答案正确... 166ms

├ 测试数据 10：答案正确... 41ms

├ 测试数据 11：答案正确... 72ms

就栈好慢啊。。。。。。。

总算学会KMP了

KMP+栈处理

匹配到长度与a相同时出栈即可

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 41ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：41ms

怎么回事？用KMP头大，用栈全过……（多亏大牛指点）

怎么回事？

幽冥剑客在说些什么啊！

Program BT;

var

Procedure die;

begin

die;

end;

begin

die;

die;

die;

Wo bu hui;

I don't know;

end.

KMP+栈即可，无须字符链表。。

若s[i]能接上去，就记录下他的前缀函数，否则全部出栈..

如果栈满了(即完全匹配)就累加,并把后M个元素退栈

写了个很强大的超时的字符链表...

怎么回事额

高级算法根本用不着，说一下我的白痴算法：

开一个10^6的大数组b，一定没问题的。

l=length(a);

然后用一个指针r标记数组b，当r>=l 时，直接比较b中从r-l+1到r的那段字符串与a是否匹配，如果匹配r直接退到r-l+1；同时计数器加一即可。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 42ms

汗死...为啥同样是链表我103ms...

丢人了...闪...

编译通过...

├ 测试数据 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+链表处理 很好很强大

其实可以不用删除的哈～

开个大数组存每个位置j的值～

匹配了之后就退到 m个字符前的j值～而i继续前进～这样其实还可以边读边做

j＝模式串指针

i＝匹配串指针

m＝模式串长度

全部 0ms AC

其实这不是我想出来的 是某个大牛想的

感谢Conan大牛出了这么好的一道题。ms是一道很弱的题，但是即使用了KMP+ansistring也不能AC，因为这道题牵扯删除操作，所以单纯调用删除函数显然就不满足我们的要求了。于是乎，Conan大牛让我长了见识：字符链表！！！单个删除操作复杂度O(1)。

结论：KMP+字符链表=AC

栈

只有一组没有秒杀

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 25ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：25ms

链表，用数组（ansistring）的话子串删除很慢

为什么字符串操作会这么慢?相当令人费解.同样的算法,用字符串操作超时,用数组居然0ms AC.怎么会这样?

太爽了，　ac了

要用一个字符　链表　再加　大名鼎鼎的　ＫＭＰ　算法

charlink=record

up,down:longint;

ch:char;

end;

ＫＭＰ　算法可参考 http://www.matrix67.com/blog/archives/115

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：运行超时...

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：0ms

这是为什么！！！！！！！！！！！！