免责声明：0460导航所展示的网站资料、数据、广告等均来自互联网,仅供大家参考。0460网站之家对可能产生的好坏结果均不承担任何责任。
- 感谢您对0460的支持与关怀！
微信公众号：www0460com&&移动版：CF 149E Martian Strings(KMP)
CF 149E Martian Strings(KMP)
发布时间： 21:31:34
编辑：www.fx114.net
本篇文章主要介绍了"CF 149E Martian Strings(KMP)"，主要涉及到CF 149E Martian Strings(KMP)方面的内容，对于CF 149E Martian Strings(KMP)感兴趣的同学可以参考一下。
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents&&&
by---cxlove &
题意：给了一个母串，然后有多个匹配串，问在母串中是否能找到不重叠两个子串，拼接成匹配串
/problemset/problem/149/E&&
我的做法是，对于每一个匹配串
正向KMP一次，记录对于匹配串的每一个长度在模式串能匹配的最左边，也就是首次匹配的位置
然后将母串和匹配串都反向，再KMP一次
然后枚举长度 ，判断是否有重叠
感觉还是不错的题，主要是KMP现在都不会了，SAD...
#include&iostream&
#include&cstdio&
#include&map&
#include&cstring&
#include&cmath&
#include&vector&
#include&algorithm&
#include&set&
#include&string&
#include&queue&
#define inf 1600005
#define M 40
#define N 100005
#define maxn 300005
#define eps 1e-12
#define zero(a) fabs(a)&eps
#define Min(a,b) ((a)&(b)?(a):(b))
#define Max(a,b) ((a)&(b)?(a):(b))
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define MOD
#define lson step&&1
#define rson step&&1|1
#define sqr(a) ((a)*(a))
#define Key_value ch[ch[root][1]][0]
#define test puts(&OK&);
#define pi acos(-1.0)
#define lowbit(x) ((-(x))&(x))
#define HASH 1331
#pragma comment(linker, &/STACK:,&)
int next[1005];
char str[100005],str_2[100005],pat[1005];
int l[1005],r[1005];
void get_next(char *s,int len){
next[0]=-1;
int i=0,j=-1;
while(i&len){
if(j==-1||s[i]==s[j]){
if(s[i]==s[j]) next[i]=next[j];
else next[i]=j;
else j=next[j];
void match(char *pat,int lp,char *str,int ls,int *dp){
int i=0,j=0;
while(i&lp&&j&ls){
if(i==-1||pat[i]==str[j]){
dp[i]=min(dp[i],j);
else i=next[i];
if(i==lp) i=next[i];
void Init(int len){
l[0]=r[0]=0;
for(int i=1;i&=i++){
int main(){
//freopen(&input.txt&,&r&,stdin);
while(scanf(&%s&,str)!=EOF){
int cnt=0,length=strlen(str);
for(int i=0;i&i++)
str_2[i]=str[length-1-i];
scanf(&%d&,&m);
while(m--){
scanf(&%s&,pat);
int len=strlen(pat);
if(len==1)
Init(len);
get_next(pat,len);
match(pat,len,str,length,l);
for(int i=0;i&len/2;i++){
swap(pat[i],pat[len-i-1]);
get_next(pat,len);
match(pat,len,str_2,length,r);
for(int i=1;i&=i++){
//cout&&i&&& &&&l[i]&&& &&&r[len-i]&&
if(l[i]+r[len-i]&=length){
printf(&%d\n&,cnt);
一、不得利用本站危害国家安全、泄露国家秘密，不得侵犯国家社会集体的和公民的合法权益，不得利用本站制作、复制和传播不法有害信息！
二、互相尊重，对自己的言论和行为负责。
本文标题：
本页链接：
