本文主要是介绍hdu2203(kmp),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
链接:点击打开链接
题意:主串是一个环,问主串中是否含模式串
代码:
#include <queue>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int siz=100005;
int nex[siz];
char S[siz<<1],T[siz];
void getnex(int tlen){int i,j;j=-1,i=0;nex[0]=-1;while(i<tlen){if(j==-1||T[i]==T[j])nex[++i]=++j;elsej=nex[j];}
}
int kmp(int slen,int tlen){int i,j;i=j=0;getnex(tlen);while(i<slen){if(j==-1||S[i]==T[j])i++,j++;elsej=nex[j];if(j==tlen)return 1;}return 0;
}
int main(){ //主串变成二倍直接kmpint i,j,slen,tlen;while(scanf("%s%s",S,T)!=EOF){slen=strlen(S);tlen=strlen(T);for(i=0;i<slen;i++)S[i+slen]=S[i];slen*=2;if(kmp(slen,tlen)==1)puts("yes");elseputs("no");}return 0;
}
这篇关于hdu2203(kmp)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!