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;
}

最新文章

  1. [Java 安全]消息摘要与数字签名
  2. Android 应用程序升级到 5.0 需要注意的问题
  3. 《TCP/IP详解 卷1:协议》读书笔记
  4. 11——在operator=中处理自我赋值
  5. POJ 1503
  6. OpenCV】透视变换 Perspective Transformation(续)
  7. c语言中的二分法
  8. VPN连接失败
  9. MFC 构建、消亡 顺序 (一)--单文档 (SDI)
  10. HDOJ2010水仙花数
  11. Open Live Writer增加代码插件
  12. [Tommas] 测试用例覆盖率(二)
  13. sphinx插入代码
  14. 磁盘工作原理与IO性能分析
  15. isNAN()的使用
  16. Centos 7 安装Docker-ce记录
  17. Node.js的进程管理
  18. websocket(三)——基于node sockit.io的即时通讯
  19. swift学习:第一个swift ui程序
  20. [Asp.net MVC]Bundle合并,压缩js、css文件

热门文章

  1. Vue-element 的 resetFields of undefined报错
  2. System.Text.Encoding.cs
  3. java代码优化写法(转摘)
  4. 使用HTTP代理
  5. logcat日志文件
  6. 如何做系列(3)-Java数据类型和MySql数据类型对照表
  7. _strupr _wcsupr _mbsupr
  8. NOIP2016提高A组 A题 礼物—概率状压dp
  9. 【一坨理论AC的题】Orz sxy大佬
  10. c++ 读取8, 10, 16进制数