【模板】KMP [2017年5月计划 清北学堂51精英班Day2]
2024-09-25 02:24:27
Day2就搞一个KMP把 马拉车、AC自动机等准备省选的时候再说。。
模板题:
1204 寻找子串位置
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 青铜 Bronze
题目描述 Description
给出字符串a和字符串b,保证b是a的一个子串,请你输出b在a中第一次出现的位置。
输入描述 Input Description
仅一行包含两个字符串a和b
输出描述 Output Description
仅一行一个整数
样例输入 Sample Input
abcd bc
样例输出 Sample Output
2
数据范围及提示 Data Size & Hint
字符串的长度均不超过100
Pascal用户请注意:两个字符串之间可能包含多个空格
洛谷上的模板题 跟我的写法有冲突(看的一个很好的博客,比着写的:)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) > (b) ? (b) : (a))
#define lowbit(a) ((a) & (-(a))) int read()
{
int x = 0;char ch = getchar();char c = ch;
while(ch > '9' || ch < '0')c = ch, ch = getchar();
while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();
if(c == '-')return -x;
return x;
} const int INF = 0x3f3f3f3f;
const int MAXN = 1000000 + 10;
const int MAXM = 1000 + 10;
int next[MAXN];char s[MAXN];char p[MAXN];
int lens,lenp; inline void init()
{
scanf("%s", s);scanf("%s", p);
lens = strlen(s);lenp = strlen(p);
}
inline void work_next()
{
int k = -1;int j = 0;
next[0] = -1;
while(j < lenp)
{
if(k == -1 ||p[k] == p[j])
{
k ++;j ++;
if(p[j] != p[k])
{
next[j] = k;
}
else
{
next[j] = next[k];
}
}
else
{
k = next[k];
}
}
}
inline int KMP(int k)
{
work_next();
int i = k;int j = 0;
while(i < lens && j < lenp)
{
if(j == -1 || s[i] == p[j])
{
i ++;j ++;
}
else
{
j = next[j];
}
}
if(j == lenp)
{
return i - j;
}
else
{
return -1;
}
}
inline void run()
{
printf("%d", KMP(0) + 1);
} int main()
{
init();
work_next();
run();
return 0;
}
最新文章
- [Java 安全]消息摘要与数字签名
- Android 应用程序升级到 5.0 需要注意的问题
- 《TCP/IP详解 卷1:协议》读书笔记
- 11——在operator=中处理自我赋值
- POJ 1503
- OpenCV】透视变换 Perspective Transformation(续)
- c语言中的二分法
- VPN连接失败
- MFC 构建、消亡 顺序 (一)--单文档 (SDI)
- HDOJ2010水仙花数
- Open Live Writer增加代码插件
- [Tommas] 测试用例覆盖率(二)
- sphinx插入代码
- 磁盘工作原理与IO性能分析
- isNAN()的使用
- Centos 7 安装Docker-ce记录
- Node.js的进程管理
- websocket(三)——基于node sockit.io的即时通讯
- swift学习:第一个swift ui程序
- [Asp.net MVC]Bundle合并,压缩js、css文件