发布时间: 2017年7月3日 11:27 最后更新: 2017年7月5日 13:46 时间限制: 500ms 内存限制: 128M
描述AA所在的国家有一项神奇的发明：插座。这里的插座不仅有两孔、三孔，而是有多种形态，下面用不同的小写字母表示不同的插座。插线板可以看做一排插座，因而下面用小写字母组成的字符串表示插线板。
该国家的用电器的插头也很特别，是由一串插头固定在一起的，下面用大写字母组成的字符串表示。只有插座和插头匹配，该用电器才能插在插线板上。例如：
插头ABCBA可以插在插线板abcbabcba上。
现在问题来了：给定插线板和插头，问该插线板上最多能插几个这样的插头？注意，这些插头不能重叠。
输入多组测试数据。 每组测试数据包含两行，第一行为插座，第二行为插头。 插座、插头对应的字符均不超过 106 。 总数据量不超过 107 个字符。
输出对每组数据，输出一行一个整数，表示答案。
样例输入1 复制 abcbabcba ABCBA 样例输出1 1 解法非常简单，直接进行KMP匹配就可以了，但是KMP的模板要有一个小小的改动（因为这里题目要求插头不能重叠），那就是只要匹配到一个插头以后，直接置j = 0这样可以避过重叠
代码：
#include <iostream> #include <cstdio> using namespace std; #define MAXN 2000001 char s[MAXN]; char str[MAXN]; int fail[MAXN]; int search(char *str) { int ans = 0; for (int i = 0, j = 0; str[i]; i++){ while (j && str[i] - 'a' != s[j] - 'A')j = fail[j - 1]; if (str[i] - 'a' == s[j] - 'A' && !s[++j]){ans++;j=0;} } return ans; } void make_fail() { for (int i = 1, j = 0; s[i]; i++){ while (j && s[i] != s[j])j = fail[j - 1]; if (s[i] == s[j])fail[i] = ++j; else fail[i] = 0; } } int main(){ while(~scanf("%s %s",str,s)){ make_fail(); printf("%d\n",search(str)); } return 0; }
