龙海市城乡规划建设局网站,网站设计说明书摘要,阿里云linux服务器搭建多个网站,网络营销推广的岗位职责有神奇插座 发布时间: 2017年7月3日 11:27 最后更新: 2017年7月5日 13:46 时间限制: 500ms 内存限制: 128M 描述 AA所在的国家有一项神奇的发明#xff1a;插座。这里的插座不仅有两孔、三孔#xff0c;而是有多种形态#xff0c;下面用不同的小写字母表示不同的插座。插… 神奇插座 发布时间: 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;j0;}}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;
}
