【CAIOJ 1178】 最长共同前缀长度
2024-09-02 05:24:38
【题目链接】
【算法】
EXKMP
【代码】
#include<bits/stdc++.h>
using namespace std;
#define MAXL 1000010 int i,N,l1,l2;
char s1[MAXL],s2[MAXL];
int extend[MAXL],next[MAXL]; template <typename T> inline void read(T &x) {
int f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
template <typename T> inline void write(T x) {
if (x < ) { putchar('-'); x = -x; }
if (x > ) write(x/);
putchar(x%+'');
}
template <typename T> inline void writeln(T x) {
write(x);
puts("");
}
inline void getnext() {
int i=,pos,j;
next[] = l2;
while (s2[i] == s2[i+] && i + < l2) i++;
next[] = i;
pos = ;
for (i = ; i < l2; i++) {
if (i + next[i-pos] < pos + next[pos]) next[i] = next[i-pos];
else {
j = pos + next[pos] - i;
if (j < ) j = ;
while (i + j < l2 && s2[j] == s2[i+j]) j++;
next[i] = j;
pos = i;
}
}
} inline void exkmp() {
int i=,pos,j;
while (s1[i] == s2[i] && i < l1 && i < l2) i++;
extend[] = i;
pos = ;
for (i = ; i < l1; i++) {
if (i + next[i-pos] < pos + extend[pos]) extend[i] = next[i-pos];
else {
j = pos + extend[pos] - i;
if (j < ) j = ;
while (i + j < l1 && j < l2 && s1[i+j] == s2[j]) j++;
extend[i] = j;
pos = i;
}
}
} int main() { scanf("%s",&s1);
scanf("%s",&s2);
l1 = strlen(s1); l2 = strlen(s2); getnext();
exkmp(); for (i = ; i < l1; i++) {
if (!i) write(extend[i]);
else {
putchar(' ');
write(extend[i]);
}
} puts(""); return ; }
最新文章
- ASP.NET MVC 5 Jquery Validate
- mix_alternates_for_parent: TRUE
- 新型编译器将原生代码转换为JavaScript
- Go support for Android
- 【IDA*】codevs 2495:水叮当的舞步
- CF 197 DIV2 Xenia and Bit Operations 线段树
- RAC 环境下参数文件(spfile)管理
- edge.js架起node.js和.net互操作桥梁
- HDU 4370 0 or 1 (最短路+最小环)
- C# ?? 运算符,不能忘记的知识点
- centos7安装codeblocks教程
- 【noip 2009】 乌龟棋 记忆化搜索&;动规
- tornado学习 - TCPClient 实现聊天功能
- 乌龟棋dp
- python coroutine
- Python_函数的有用信息、带参数的装饰器、多个装饰器装饰一个函数
- python - 练习统计随机字母数据
- 安装Anaconda以及jupyter的使用
- Redis4.0模块子系统实现简述
- dubbo和zookeeper的关系
热门文章
- ROS节点分布式运行方法
- python的__name__和dir()属性
- Nginx配置文件语法教程
- 前端微服务-面向web平台级应用的设计
- 一根数据线玩转树莓派Zero
- qt动画入门
- jquery 获取下拉框 某个text=&#39;xxx&#39;的option的属性 非选中 如何获得select被选中option的value和text和......
- 【转载】C#中回滚TransactionScope的使用方法和原理
- phpExcel大数据量情况下内存溢出解决
- 初识glib(1)