hdu2203kmp匹配
2024-10-08 21:29:29
拼接字符串即可解决移位的问题;
代码如下:
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
#define pf printf
#define mem(a,b) memset(a,b,sizeof(a))
#define prime1 1e9+7
#define prime2 1e9+9
#define pi 3.14159265
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define scand(x) scanf("%llf",&x)
#define f(i,a,b) for(int i=a;i<=b;i++)
#define scan(a) scanf("%d",&a)
#define dbg(args) cout<<#args<<":"<<args<<endl;
#define inf 0x3f3f3f3f
#define maxn 1000010
int n,m,t;
char s[maxn],p[maxn],nxt[maxn];
void getnxt()
{
nxt[]=-;
int i=-,j=;
while(j<strlen(p))
{
if(i==-||p[i]==p[j])
{
i++,j++;
if(p[i]==p[j])nxt[j]=nxt[i];
else nxt[j]=i;
}
else i=nxt[i];
}
}
void kmp()
{
int plen=strlen(p);
int slen=strlen(s);
int i=,j=;
while(i<slen)
{
if(j==-||s[i]==p[j])i++,j++;
else j=nxt[j];
if(j==plen)
{
pf("yes\n");
return;
}
}
pf("no\n");
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
std::ios::sync_with_stdio(false);
while(scanf("%s %s",s,p)==)
{
if(strlen(s)<strlen(p))pf("no\n");
else{
int len=strlen(s);
f(i,,len-)s[len+i]=s[i];//解除循环
getnxt();
kmp();
}
}
}
最新文章
- ABP源码分析三十:ABP.RedisCache
- linux 安装配置Nginx
- 网上找的Gif图片解析类
- php面试题及答案
- grub的sol
- iOS——使用StroryBoard页面跳转及传值
- 测试驱动开发(Test-Driven Development,简称TDD)--单元测试-->;提高代码质量
- SCCM 客户端的修复
- Access应用日志<;一>;
- Codeforce 493c
- URAL 1658. Sum of Digits(DP)
- iOS-多线程--(pthread/NSThread/GCD/NSOperation)--总结
- 【spring 区别】ClassXmlAplicationContext和FileSystemXmlApplicationContext的区别
- MVC中”从客户端检测到有潜在危险的Request.Form值“的解决方法
- python程序中自启动appium服务
- c#配置log4net步骤
- web.xml文件中配置ShallowEtagHeaderFilter需注意的问题
- UVALIVE 3026 Period
- MFC 双缓冲加载背景
- 使用docker-compose搭建AspNetCore开发环境