2015 四川省赛 C Censor(哈希 | KMP)
2024-08-27 19:26:57
模式串为子串
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
最新文章
- Python 类(一)
- Birt导出Excel图片
- c语言 动态数组
- Unity3D编程回忆录,Unity3d视频教程,教父团队倾情之作
- java的通信机制
- Android Studio 没有assets目录的问题
- Spring Security4实例(Java config 版) —— Remember-Me
- MySQL binlog相关分析
- 第64节:Java中的Spring Boot 2.0简介笔记
- 在eclipse中,使用spring tool suite配置spring环境
- Exception 04 : java.lang.ClassNotFoundException: Could not load requested class : org.hsqldb.jdbcDriver
- Graph database_neo4j 底层存储结构分析(2)
- python-day41--数据库---数据类型
- HTML结构组成
- HDU 1316 (斐波那契数列,大数相加,大数比较大小)
- cogs 1330 [HNOI2008]玩具装箱toy
- Unalignable boolean Series provided as indexer (index of the boolean Series and of the indexed object do not match
- java timer timertask mark
- linux上nginx上配置虚拟主机的相关配置
- ES6的新特性(3)——变量的解构赋值
热门文章
- Codeforces 343D Water Tree & 树链剖分教程
- node.js实现web解析dns
- Apicloud_(接口验证)用户注册头部信息X-APICloud-AppKey生成
- R_Studio(聚类)针对iris数据比较几种聚类方法优劣
- 应对高并发场景的redis加锁技巧
- C++入门经典-例3.20-使用continue跳出循环
- eclipse中解决update maven之后jre被改成1.5的问题
- Custom Configuration 的两种方法:1.Configuration Sections
- 使用putty远程登录Ubuntu时,报Network error:Connection refused错误及解决(记录)
- 【ABAP系列】SAP ABAP 资产类BAPI过账 BAPI_ACC_DOCUMENT_POST