模式串为子串

KMP

/*

@author : victor

*/

#include <bits/stdc++.h>
using namespace std; typedef long long ll;
const int MAX = 5e6 + ; int next_[MAX];
char s1[MAX], s2[MAX], ans[MAX];
int pos[MAX];
int l1, l2, cnt; void get_next(char x[],int m,int next_[])
{
int i ,j;
j = next_[] = -;
i = ;
while(i < m){
while(-!=j&&x[i]!=x[j]) j = next_[j];
next_[++i] = ++j;
}
} void KMP(){
int i = , j = ;
cnt = ;
while(s1[i] != '\0')
{
ans[cnt] = s1[i ++];
while(!(j == - || ans[cnt] == s2[j]))
j = next_[j];
j ++;
cnt ++;
pos[cnt] = j;
if(j >= l2)
{
cnt -= l2;
j = pos[cnt];
}
}
} int main()
{
while(scanf("%s %s", s2, s1) != EOF)
{
l1 = strlen(s1);
l2 = strlen(s2);
get_next(s2,l2,next_);
KMP();
for(int i = ; i < cnt; i++)
printf("%c", ans[i]);
printf("\n");
}
} // A B C A B C A B C
// -1 0 0 0 1 2 3 4 5 6
// A B C B C C B A C

最新文章

  1. Python 类(一)
  2. Birt导出Excel图片
  3. c语言 动态数组
  4. Unity3D编程回忆录,Unity3d视频教程,教父团队倾情之作
  5. java的通信机制
  6. Android Studio 没有assets目录的问题
  7. Spring Security4实例(Java config 版) —— Remember-Me
  8. MySQL binlog相关分析
  9. 第64节:Java中的Spring Boot 2.0简介笔记
  10. 在eclipse中,使用spring tool suite配置spring环境
  11. Exception 04 : java.lang.ClassNotFoundException: Could not load requested class : org.hsqldb.jdbcDriver
  12. Graph database_neo4j 底层存储结构分析(2)
  13. python-day41--数据库---数据类型
  14. HTML结构组成
  15. HDU 1316 (斐波那契数列,大数相加,大数比较大小)
  16. cogs 1330 [HNOI2008]玩具装箱toy
  17. Unalignable boolean Series provided as indexer (index of the boolean Series and of the indexed object do not match
  18. java timer timertask mark
  19. linux上nginx上配置虚拟主机的相关配置
  20. ES6的新特性(3)——变量的解构赋值

热门文章

  1. Codeforces 343D Water Tree & 树链剖分教程
  2. node.js实现web解析dns
  3. Apicloud_(接口验证)用户注册头部信息X-APICloud-AppKey生成
  4. R_Studio(聚类)针对iris数据比较几种聚类方法优劣
  5. 应对高并发场景的redis加锁技巧
  6. C++入门经典-例3.20-使用continue跳出循环
  7. eclipse中解决update maven之后jre被改成1.5的问题
  8. Custom Configuration 的两种方法:1.Configuration Sections
  9. 使用putty远程登录Ubuntu时,报Network error:Connection refused错误及解决(记录)
  10. 【ABAP系列】SAP ABAP 资产类BAPI过账 BAPI_ACC_DOCUMENT_POST