Posts tagged with KMP


CCPC网络赛的KMP模板题…… 比赛期间因为被1003卡住了,这道题根本没时间去想…… 本来一眼看去我也是想到AC自动机,只要吧字符串反转一下,就可以套用上一次的AC自动机直接求解。 但是模式串和匹配串都只有一个,建立AC自动机虽然可解,但有不必要的消耗。 这道题几乎卡掉了除了KMP以外的所有求这道题的其他解法。 题意: 给你两个串a , b,要你找出 b 串的所有后缀同时也是 a 串的子串。 然后按题意计算。 思路: 其实还是和上一道AC自动机有些类似之处。 但还是有很大不同,AC自动机可以在匹配的时候不断 fail 到前缀。…

专题链接 KMP专题(一) KMP专题(二) HDU 3336 Count the string 题意: 事先说好,这题数据非常弱,典型的想的比出的简单,各种错误代码都能A。 这道题的题意是让你找出所有前缀在整个字符串中的子串数量。 思路: 这里只提供所谓出题人的思路,水水过去就算了啊。 对于一个位置,如果他的next数组不是0,说明这个后缀与前缀有匹配。注意这里是后缀,而不是在整个字符串范围内。然而这个思路还是A了。…

专题链接 KMP专题(一) KMP专题(三) HUST 1010 The Minimum Length 题意: 找最小循环节长度。 思路: 无。 #include <algorithm> #include <cctype> #include <cstdio&…

前言 OK,刷专题终于刷到了自己不会的最小表示法,在学习最小表示法之前,稍微总结一下。 kmp多水题,而且因为挂在hdu和poj上,本身有些数据也非常水,所以打算开个专题来汇总一下这些水题。 KMP专题链接 KMP专题(一) KMP专题(三) 题解 HDU 1711 Number Sequence 题意: 返回第一个数字序列匹配的位置。 思路: KMP入门题。 AC Code…

KMP的一个第一个小应用,求循环节。 昨天开始学字符串,晚上的时候看了很多博客,但都讲的很乱,很复杂,直到看到了这篇 (传送门) 最后在纸上跟着模拟了一下,才算个人意义上的理解了。包括一个小优化。 这道题只有你理解了kmp的next的数组求法才会做。 题意: 一串珠子,要你再加最少的珠子满足,珠子循环大于等于2。比如abcabc,你只能在左右两边加。 思路: kmp的next数组保存的是以当前位置的前一位置结尾的字符串中最长的相同前后缀长度。 因为字符串是循环的,比如abcabcab,那么 中间的abc 为前后缀所共有,…