Java学习指南
  • Java 编程的逻辑
  • Java进阶
  • Java FrameWorks
  • 了解 USB Type-A,B,C 三大标准接口
  • 深入浅出DDD
  • 重构:改善既有代码的设计
  • 面试大纲
  • 云原生
    • 什么是无服务器(what is serverless)?
  • 博客
    • 深入分析Log4j 漏洞
  • 博客
    • Serverless之快速搭建Spring Boot应用
  • 博客
    • 使用 Prometheus + Grafana + Spring Boot Actuator 监控应用
  • 博客
    • 使用 Prometheus + Grafana 监控 MySQL
  • 博客
    • 使用Github Actions + Docker 部署Spring Boot应用
  • 博客
    • Redis分布式锁之Redisson的原理和实践
  • 博客
    • 数据库中的树结构应该怎样去设计
  • 学习&成长
    • 如何成为技术大牛
  • 开发工具
    • Git Commit Message Guidelines
  • 开发工具
    • git命名大全
  • 开发工具
    • Gradle vs Maven Comparison
  • 开发工具
    • Swagger2常用注解及其说明
  • 开发工具
    • 简明 VIM 练级攻略
  • 微服务
    • 十大微服务设计模式和原则
  • 微服务
    • 微服务下的身份认证和令牌管理
  • 微服务
    • 微服务坏味道之循环依赖
  • 设计模式
    • 设计模式 - JDK中的设计模式
  • 设计模式
    • 设计模式 - Java三种代理模式
  • 设计模式
    • 设计模式 - 六大设计原则
  • 设计模式
    • 设计模式 - 单例模式
  • 设计模式
    • 设计模式 - 命名模式
  • 设计模式
    • 设计模式 - 备忘录模式
  • 设计模式
    • 设计模式 - 概览
  • 设计模式
    • 设计模式 - 没用的设计模式
  • 质量&效率
    • Homebrew 替换国内镜像源
  • 质量&效率
    • 工作中如何做好技术积累
  • Java FrameWorks
    • Logback
      • 自定义 logback 日志过滤器
  • Java FrameWorks
    • Mybatis
      • MyBatis(十三) - 整合Spring
  • Java FrameWorks
    • Mybatis
      • MyBatis(十二) - 一些API
  • Java FrameWorks
    • Mybatis
      • Mybatis(一) - 概述
  • Java FrameWorks
    • Mybatis
      • Mybatis(七) - 结果集的封装与映射
  • Java FrameWorks
    • Mybatis
      • Mybatis(三) - mapper.xml及其加载机制
  • Java FrameWorks
    • Mybatis
      • Mybatis(九) - 事务
  • Java FrameWorks
    • Mybatis
      • Mybatis(二) - 全局配置文件及其加载机制
  • Java FrameWorks
    • Mybatis
      • Mybatis(五) - SqlSession执行流程
  • Java FrameWorks
    • Mybatis
      • Mybatis(八) - 缓存
  • Java FrameWorks
    • Mybatis
      • Mybatis(六) - 动态SQL的参数绑定与执行
  • Java FrameWorks
    • Mybatis
      • Mybatis(十) - 插件
  • Java FrameWorks
    • Mybatis
      • Mybatis(十一) - 日志
  • Java FrameWorks
    • Mybatis
      • Mybatis(四) - Mapper接口解析
  • Java FrameWorks
    • Netty
      • Netty 可靠性分析
  • Java FrameWorks
    • Netty
      • Netty - Netty 线程模型
  • Java FrameWorks
    • Netty
      • Netty堆外内存泄露排查盛宴
  • Java FrameWorks
    • Netty
      • Netty高级 - 高性能之道
  • Java FrameWorks
    • Shiro
      • Shiro + JWT + Spring Boot Restful 简易教程
  • Java FrameWorks
    • Shiro
      • 非常详尽的 Shiro 架构解析!
  • Java FrameWorks
    • Spring
      • Spring AOP 使用介绍,从前世到今生
  • Java FrameWorks
    • Spring
      • Spring AOP 源码解析
  • Java FrameWorks
    • Spring
      • Spring Event 实现原理
  • Java FrameWorks
    • Spring
      • Spring Events
  • Java FrameWorks
    • Spring
      • Spring IOC容器源码分析
  • Java FrameWorks
    • Spring
      • Spring Integration简介
  • Java FrameWorks
    • Spring
      • Spring MVC 框架中拦截器 Interceptor 的使用方法
  • Java FrameWorks
    • Spring
      • Spring bean 解析、注册、实例化流程源码剖析
  • Java FrameWorks
    • Spring
      • Spring validation中@NotNull、@NotEmpty、@NotBlank的区别
  • Java FrameWorks
    • Spring
      • Spring 如何解决循环依赖?
  • Java FrameWorks
    • Spring
      • Spring 异步实现原理与实战分享
  • Java FrameWorks
    • Spring
      • Spring中的“for update”问题
  • Java FrameWorks
    • Spring
      • Spring中的设计模式
  • Java FrameWorks
    • Spring
      • Spring事务失效的 8 大原因
  • Java FrameWorks
    • Spring
      • Spring事务管理详解
  • Java FrameWorks
    • Spring
      • Spring计时器StopWatch使用
  • Java FrameWorks
    • Spring
      • 详述 Spring MVC 框架中拦截器 Interceptor 的使用方法
  • Java FrameWorks
    • Spring
      • 透彻的掌握 Spring 中@transactional 的使用
  • Java
    • Java IO&NIO&AIO
      • Java IO - BIO 详解
  • Java
    • Java IO&NIO&AIO
      • Java NIO - IO多路复用详解
  • Java
    • Java IO&NIO&AIO
      • Java N(A)IO - Netty
  • Java
    • Java IO&NIO&AIO
      • Java IO - Unix IO模型
  • Java
    • Java IO&NIO&AIO
      • Java IO - 分类
  • Java
    • Java IO&NIO&AIO
      • Java NIO - 基础详解
  • Java
    • Java IO&NIO&AIO
      • Java IO - 常见类使用
  • Java
    • Java IO&NIO&AIO
      • Java AIO - 异步IO详解
  • Java
    • Java IO&NIO&AIO
      • Java IO概述
  • Java
    • Java IO&NIO&AIO
      • Java IO - 设计模式
  • Java
    • Java IO&NIO&AIO
      • Java NIO - 零拷贝实现
  • Java
    • Java JVM
      • JVM 优化经验总结
  • Java
    • Java JVM
      • JVM 内存结构
  • Java
    • Java JVM
      • JVM参数设置
  • Java
    • Java JVM
      • Java 内存模型
  • Java
    • Java JVM
      • 从实际案例聊聊Java应用的GC优化
  • Java
    • Java JVM
      • Java 垃圾回收器G1详解
  • Java
    • Java JVM
      • 垃圾回收器Shenandoah GC详解
  • Java
    • Java JVM
      • 垃圾回收器ZGC详解
  • Java
    • Java JVM
      • 垃圾回收基础
  • Java
    • Java JVM
      • 如何优化Java GC
  • Java
    • Java JVM
      • 类加载机制
  • Java
    • Java JVM
      • 类字节码详解
  • Java
    • Java 基础
      • Java hashCode() 和 equals()
  • Java
    • Java 基础
      • Java 基础 - Java native方法以及JNI实践
  • Java
    • Java 基础
      • Java serialVersionUID 有什么作用?
  • Java
    • Java 基础
      • Java 泛型的类型擦除
  • Java
    • Java 基础
      • Java 基础 - Unsafe类解析
  • Java
    • Java 基础
      • Difference Between Statement and PreparedStatement
  • Java
    • Java 基础
      • Java 基础 - SPI机制详解
  • Java
    • Java 基础
      • Java 基础 - final
  • Java
    • Java 基础
      • Java中static关键字详解
  • Java
    • Java 基础
      • 为什么说Java中只有值传递?
  • Java
    • Java 基础
      • Java 基础 - 即时编译器原理解析及实践
  • Java
    • Java 基础
      • Java 基础 - 反射
  • Java
    • Java 基础
      • Java多态的面试题
  • Java
    • Java 基础
      • Java 基础 - 异常机制详解
  • Java
    • Java 基础
      • 为什么要有抽象类?
  • Java
    • Java 基础
      • 接口的本质
  • Java
    • Java 基础
      • Java 基础 - 枚举
  • Java
    • Java 基础
      • Java 基础 - 泛型机制详解
  • Java
    • Java 基础
      • Java 基础 - 注解机制详解
  • Java
    • Java 基础
      • 为什么 String hashCode 方法选择数字31作为乘子
  • Java
    • Java 并发
      • Java 并发 - 14个Java并发容器
  • Java
    • Java 并发
      • Java 并发 - AQS
  • Java
    • Java 并发
      • Java 并发 - BlockingQueue
  • Java
    • Java 并发
      • Java 并发 - CAS
  • Java
    • Java 并发
      • Java 并发 - Condition接口
  • Java
    • Java 并发
      • Java 并发 - CopyOnWriteArrayList
  • Java
    • Java 并发
      • Java 并发 - CountDownLatch、CyclicBarrier和Phaser对比
  • Java
    • Java 并发
      • Java 并发 - Fork&Join框架
  • Java
    • Java 并发
      • Java 并发 - Java CompletableFuture 详解
  • Java
    • Java 并发
      • Java 并发 - Java 线程池
  • Java
    • Java 并发
      • Java 并发 - Lock接口
  • Java
    • Java 并发
      • Java 并发 - ReentrantLock
  • Java
    • Java 并发
      • Java 并发 - ReentrantReadWriteLock
  • Java
    • Java 并发
      • Java 并发 - Synchronized
  • Java
    • Java 并发
      • Java 并发 - ThreadLocal 内存泄漏问题
  • Java
    • Java 并发
      • Java 并发 - ThreadLocal
  • Java
    • Java 并发
      • Java 并发 - Volatile
  • Java
    • Java 并发
      • Java 并发 - 从ReentrantLock的实现看AQS的原理及应用
  • Java
    • Java 并发
      • Java 并发 - 公平锁和非公平锁
  • Java
    • Java 并发
      • Java 并发 - 内存模型
  • Java
    • Java 并发
      • Java 并发 - 原子类
  • Java
    • Java 并发
      • Java 并发 - 如何确保三个线程顺序执行?
  • Java
    • Java 并发
      • Java 并发 - 锁
  • Java
    • Java 的新特性
      • Java 10 新特性概述
  • Java
    • Java 的新特性
      • Java 11 新特性概述
  • Java
    • Java 的新特性
      • Java 12 新特性概述
  • Java
    • Java 的新特性
      • Java 13 新特性概述
  • Java
    • Java 的新特性
      • Java 14 新特性概述
  • Java
    • Java 的新特性
      • Java 15 新特性概述
  • Java
    • Java 的新特性
      • Java 8的新特性
  • Java
    • Java 的新特性
      • Java 9 新特性概述
  • Java
    • Java 调试排错
      • 调试排错 - Java Debug Interface(JDI)详解
  • Java
    • Java 调试排错
      • 调试排错 - CPU 100% 排查优化实践
  • Java
    • Java 调试排错
      • 调试排错 - Java Heap Dump分析
  • Java
    • Java 调试排错
      • 调试排错 - Java Thread Dump分析
  • Java
    • Java 调试排错
      • 调试排错 - Java动态调试技术原理
  • Java
    • Java 调试排错
      • 调试排错 - Java应用在线调试Arthas
  • Java
    • Java 调试排错
      • 调试排错 - Java问题排查:工具单
  • Java
    • Java 调试排错
      • 调试排错 - 内存溢出与内存泄漏
  • Java
    • Java 调试排错
      • 调试排错 - 在线分析GC日志的网站GCeasy
  • Java
    • Java 调试排错
      • 调试排错 - 常见的GC问题分析与解决
  • Java
    • Java 集合
      • Java 集合 - ArrayList
  • Java
    • Java 集合
      • Java 集合 - HashMap 和 ConcurrentHashMap
  • Java
    • Java 集合
      • Java 集合 - HashMap的死循环问题
  • Java
    • Java 集合
      • Java 集合 - LinkedHashSet&Map
  • Java
    • Java 集合
      • Java 集合 - LinkedList
  • Java
    • Java 集合
      • Java 集合 - PriorityQueue
  • Java
    • Java 集合
      • Java 集合 - Stack & Queue
  • Java
    • Java 集合
      • Java 集合 - TreeSet & TreeMap
  • Java
    • Java 集合
      • Java 集合 - WeakHashMap
  • Java
    • Java 集合
      • Java 集合 - 为什么HashMap的容量是2的幂次方
  • Java
    • Java 集合
      • Java 集合 - 概览
  • Java
    • Java 集合
      • Java 集合 - 高性能队列Disruptor详解
  • 分布式
    • RPC
      • ⭐️RPC - Dubbo&hsf&Spring cloud的区别
  • 分布式
    • RPC
      • ⭐️RPC - Dubbo的架构原理
  • 分布式
    • RPC
      • ⭐️RPC - HSF的原理分析
  • 分布式
    • RPC
      • ⭐️RPC - 你应该知道的RPC原理
  • 分布式
    • RPC
      • ⭐️RPC - 动态代理
  • 分布式
    • RPC
      • 深入理解 RPC 之协议篇
  • 分布式
    • RPC
      • RPC - 序列化和反序列化
  • 分布式
    • RPC
      • ⭐️RPC - 服务注册与发现
  • 分布式
    • RPC
      • RPC - 核心原理
  • 分布式
    • RPC
      • ⭐️RPC - 框架对比
  • 分布式
    • RPC
      • ⭐️RPC - 网络通信
  • 分布式
    • 分布式事务
      • 分布式事务 Seata TCC 模式深度解析
  • 分布式
    • 分布式事务
      • 分布式事务的实现原理
  • 分布式
    • 分布式事务
      • 常用的分布式事务解决方案
  • 分布式
    • 分布式事务
      • 手写实现基于消息队列的分布式事务框架
  • 分布式
    • 分布式算法
      • CAP 定理的含义
  • 分布式
    • 分布式算法
      • Paxos和Raft比较
  • 分布式
    • 分布式算法
      • 分布式一致性与共识算法
  • 分布式
    • 分布式锁
      • ⭐️分布式锁的原理及实现方式
  • 分布式
    • 搜索引擎
      • ElasticSearch与SpringBoot的集成与JPA方法的使用
  • 分布式
    • 搜索引擎
      • 全文搜索引擎 Elasticsearch 入门教程
  • 分布式
    • 搜索引擎
      • 十分钟学会使用 Elasticsearch 优雅搭建自己的搜索系统
  • 分布式
    • 搜索引擎
      • 腾讯万亿级 Elasticsearch 技术解密
  • 分布式
    • 日志系统
      • Grafana Loki 简明教程
  • 分布式
    • 日志系统
      • 分布式系统中如何优雅地追踪日志
  • 分布式
    • 日志系统
      • 如何优雅地记录操作日志?
  • 分布式
    • 日志系统
      • 日志收集组件—Flume、Logstash、Filebeat对比
  • 分布式
    • 日志系统
      • 集中式日志系统 ELK 协议栈详解
  • 分布式
    • 消息队列
      • 消息队列 - Kafka
  • 分布式
    • 消息队列
      • 消息队列 - Kafka、RabbitMQ、RocketMQ等消息中间件的对比
  • 分布式
    • 消息队列
      • 消息队列之 RabbitMQ
  • 分布式
    • 消息队列
      • 消息队列 - 使用docker-compose构建kafka集群
  • 分布式
    • 消息队列
      • 消息队列 - 分布式系统与消息的投递
  • 分布式
    • 消息队列
      • 消息队列 - 如何保证消息的可靠性传输
  • 分布式
    • 消息队列
      • 消息队列 - 如何保证消息的顺序性
  • 分布式
    • 消息队列
      • 消息队列 - 如何保证消息队列的高可用
  • 分布式
    • 消息队列
      • 消息队列 - 消息队列设计精要
  • 分布式
    • 监控系统
      • 深度剖析开源分布式监控CAT
  • 大数据
    • Flink
      • Flink架构与核心组件
  • 微服务
    • Dubbo
      • 基于dubbo的分布式应用中的统一异常处理
  • 微服务
    • Dubbo
      • Vim快捷键
  • 微服务
    • Service Mesh
      • Istio 是什么?
  • 微服务
    • Service Mesh
      • OCTO 2.0:美团基于Service Mesh的服务治理系统详解
  • 微服务
    • Service Mesh
      • Service Mesh是什么?
  • 微服务
    • Service Mesh
      • Spring Cloud向Service Mesh迁移
  • 微服务
    • Service Mesh
      • 数据挖掘算法
  • 微服务
    • Service Mesh
      • Seata Saga 模式
  • 微服务
    • Spring Cloud
      • Seata TCC 模式
  • 微服务
    • Spring Cloud
      • Spring Cloud Config
  • 微服务
    • Spring Cloud
      • Seata AT 模式
  • 微服务
    • Spring Cloud
      • Spring Cloud Gateway
  • 微服务
    • Spring Cloud
      • Spring Cloud OpenFeign 的核心原理
  • 微服务
    • Spring Cloud
      • Seata XA 模式
  • 数据库
    • Database Version Control
      • Liquibase vs. Flyway
  • 数据库
    • Database Version Control
      • Six reasons to version control your database
  • 数据库
    • MySQL
      • How Sharding Works
  • 数据库
    • MySQL
      • MySQL InnoDB中各种SQL语句加锁分析
  • 数据库
    • MySQL
      • MySQL 事务隔离级别和锁
  • 数据库
    • MySQL
      • MySQL 索引性能分析概要
  • 数据库
    • MySQL
      • MySQL 索引设计概要
  • 数据库
    • MySQL
      • MySQL出现Waiting for table metadata lock的原因以及解决方法
  • 数据库
    • MySQL
      • MySQL的Limit性能问题
  • 数据库
    • MySQL
      • MySQL索引优化explain
  • 数据库
    • MySQL
      • MySQL索引背后的数据结构及算法原理
  • 数据库
    • MySQL
      • MySQL行转列、列转行问题
  • 数据库
    • MySQL
      • 一条SQL更新语句是如何执行的?
  • 数据库
    • MySQL
      • 一条SQL查询语句是如何执行的?
  • 数据库
    • MySQL
      • 为什么 MySQL 使用 B+ 树
  • 数据库
    • MySQL
      • 为什么 MySQL 的自增主键不单调也不连续
  • 数据库
    • MySQL
      • 为什么我的MySQL会“抖”一下?
  • 数据库
    • MySQL
      • 为什么数据库不应该使用外键
  • 数据库
    • MySQL
      • 为什么数据库会丢失数据
  • 数据库
    • MySQL
      • 事务的可重复读的能力是怎么实现的?
  • 数据库
    • MySQL
      • 大众点评订单系统分库分表实践
  • 数据库
    • MySQL
      • 如何保证缓存与数据库双写时的数据一致性?
  • 数据库
    • MySQL
      • 浅谈数据库并发控制 - 锁和 MVCC
  • 数据库
    • MySQL
      • 深入浅出MySQL 中事务的实现
  • 数据库
    • MySQL
      • 浅入浅出MySQL 和 InnoDB
  • 数据库
    • PostgreSQL
      • PostgreSQL upsert功能(insert on conflict do)的用法
  • 数据库
    • Redis
      • Redis GEO & 实现原理深度分析
  • 数据库
    • Redis
      • Redis 和 I/O 多路复用
  • 数据库
    • Redis
      • Redis分布式锁
  • 数据库
    • Redis
      • Redis实现分布式锁中的“坑”
  • 数据库
    • Redis
      • Redis总结
  • 数据库
    • Redis
      • 史上最全Redis高可用技术解决方案大全
  • 数据库
    • Redis
      • Redlock:Redis分布式锁最牛逼的实现
  • 数据库
    • Redis
      • 为什么 Redis 选择单线程模型
  • 数据库
    • TiDB
      • 新一代数据库TiDB在美团的实践
  • 数据库
    • 数据仓库
      • 实时数仓在有赞的实践
  • 数据库
    • 数据库原理
      • OLTP与OLAP的关系是什么?
  • 数据库
    • 数据库原理
      • 为什么 OLAP 需要列式存储
  • 系统设计
    • DDD
      • Domain Primitive
  • 系统设计
    • DDD
      • Repository模式
  • 系统设计
    • DDD
      • 应用架构
  • 系统设计
    • DDD
      • 聊聊如何避免写流水账代码
  • 系统设计
    • DDD
      • 领域层设计规范
  • 系统设计
    • DDD
      • 从三明治到六边形
  • 系统设计
    • DDD
      • 阿里盒马领域驱动设计实践
  • 系统设计
    • DDD
      • 领域驱动设计(DDD)编码实践
  • 系统设计
    • DDD
      • 领域驱动设计在互联网业务开发中的实践
  • 系统设计
    • 基础架构
      • 容错,高可用和灾备
  • 系统设计
    • 数据聚合
      • GraphQL及元数据驱动架构在后端BFF中的实践
  • 系统设计
    • 数据聚合
      • 高效研发-闲鱼在数据聚合上的探索与实践
  • 系统设计
    • 服务安全
      • JSON Web Token 入门教程
  • 系统设计
    • 服务安全
      • 你还在用JWT做身份认证嘛?
  • 系统设计
    • 服务安全
      • 凭证(Credentials)
  • 系统设计
    • 服务安全
      • 授权(Authorization)
  • 系统设计
    • 服务安全
      • 理解OAuth2.0
  • 系统设计
    • 服务安全
      • 认证(Authentication)
  • 系统设计
    • 架构案例
      • 微信 Android 客户端架构演进之路
  • 系统设计
    • 高可用架构
      • 业务高可用的保障:异地多活架构
  • 计算机基础
    • 字符编码
      • Base64原理解析
  • 计算机基础
    • 字符编码
      • 字符编码笔记:ASCII,Unicode 和 UTF-8
  • 计算机基础
    • 操作系统
      • 为什么 CPU 访问硬盘很慢
  • 计算机基础
    • 操作系统
      • 为什么 HTTPS 需要 7 次握手以及 9 倍时延
  • 计算机基础
    • 操作系统
      • 为什么 Linux 默认页大小是 4KB
  • 计算机基础
    • 操作系统
      • 磁盘IO那些事
  • 计算机基础
    • 操作系统
      • 虚拟机的3种网络模式
  • 计算机基础
    • 服务器
      • mac终端bash、zsh、oh-my-zsh最实用教程
  • 计算机基础
    • 服务器
      • Nginx强制跳转Https
  • 计算机基础
    • 服务器
      • curl 的用法指南
  • 计算机基础
    • 网络安全
      • 如何设计一个安全的对外接口?
  • 计算机基础
    • 网络安全
      • 浅谈常见的七种加密算法及实现
  • 计算机基础
    • 网络编程
      • MQTT - The Standard for IoT Messaging
  • 计算机基础
    • 网络编程
      • 两万字长文 50+ 张趣图带你领悟网络编程的内功心法
  • 计算机基础
    • 网络编程
      • 为什么 TCP 协议有 TIME_WAIT 状态
  • 计算机基础
    • 网络编程
      • 为什么 TCP 协议有性能问题
  • 计算机基础
    • 网络编程
      • 为什么 TCP 协议有粘包问题
  • 计算机基础
    • 网络编程
      • 为什么 TCP 建立连接需要三次握手
  • 计算机基础
    • 网络编程
      • 为什么 TCP/IP 协议会拆分数据
  • 计算机基础
    • 网络编程
      • 使用 OAuth 2 和 JWT 为微服务提供安全保障
  • 计算机基础
    • 网络编程
      • 四种常见的 POST 提交数据方式
  • 计算机基础
    • 网络编程
      • 有赞TCP网络编程最佳实践
  • 计算机基础
    • 网络编程
      • 看完这篇HTTP,跟面试官扯皮就没问题了
  • 计算机基础
    • 网络编程
      • 详细解析 HTTP 与 HTTPS 的区别
  • 质量&效率
    • 快捷键
      • Idea快捷键(Mac版)
  • 质量&效率
    • 快捷键
      • Shell快捷键
  • 质量&效率
    • 快捷键
      • conduit
  • 质量&效率
    • 敏捷开发
      • Scrum的3种角色
  • 质量&效率
    • 敏捷开发
      • Scrum的4种会议
  • 质量&效率
    • 敏捷开发
      • ThoughtWorks的敏捷开发
  • 质量&效率
    • 敏捷开发
      • 敏捷开发入门教程
  • 运维&测试
    • Docker
      • Docker (容器) 的原理
  • 运维&测试
    • Docker
      • Docker Compose:链接外部容器的几种方式
  • 运维&测试
    • Docker
      • Docker 入门教程
  • 运维&测试
    • Docker
      • Docker 核心技术与实现原理
  • 运维&测试
    • Docker
      • Dockerfile 最佳实践
  • 运维&测试
    • Docker
      • Docker开启Remote API 访问 2375端口
  • 运维&测试
    • Docker
      • Watchtower - 自动更新 Docker 镜像与容器
  • 运维&测试
    • Kubernetes
      • Kubernetes 介绍
  • 运维&测试
    • Kubernetes
      • Kubernetes 在有赞的实践
  • 运维&测试
    • Kubernetes
      • Kubernetes 学习路径
  • 运维&测试
    • Kubernetes
      • Kubernetes如何改变美团的云基础设施?
  • 运维&测试
    • Kubernetes
      • Kubernetes的三种外部访问方式:NodePort、LoadBalancer 和 Ingress
  • 运维&测试
    • Kubernetes
      • 谈 Kubernetes 的架构设计与实现原理
  • 运维&测试
    • 压测
      • 全链路压测平台(Quake)在美团中的实践
  • 运维&测试
    • 测试
      • Cpress - JavaScript End to End Testing Framework
  • 运维&测试
    • 测试
      • 代码覆盖率-JaCoCo
  • 运维&测试
    • 测试
      • 浅谈代码覆盖率
  • 运维&测试
    • 测试
      • 测试中 Fakes、Mocks 以及 Stubs 概念明晰
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP中的Bean是如何被AOP代理的
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP原生动态代理和Cglib动态代理
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP实现方式(xml&注解)
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP是如何收集切面类并封装的
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP概述
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP的底层核心后置处理器
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP的延伸知识
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - IOC(一)
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - IOC(三)
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - IOC(二)
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - IOC(五)
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - IOC(四) - 循环依赖与解决方案
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - 启动引导
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot JarLauncher
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot Web Mvc 自动装配
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot 使用ApplicationListener监听器
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot 声明式事务
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot 嵌入式容器
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot引起的“堆外内存泄漏”排查及经验总结
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot的启动流程
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot自动化配置源码分析
  • Java FrameWorks
    • Spring
      • Spring Boot
        • 如何自定义Spring Boot Starter?
  • Java FrameWorks
    • Spring
      • Spring IOC
        • IOC - 模块装配和条件装配
  • Java FrameWorks
    • Spring
      • Spring IOC
        • IOC - 配置源(xml,注解)
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Environment
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring ApplicationContext
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring BeanDefinition
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring BeanFactory
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring BeanFactoryPostProcessor
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring BeanPostProcessor
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Bean的生命周期(一) - 概述
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Bean的生命周期(三) - 实例化阶段
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Bean的生命周期(二) - BeanDefinition
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Bean的生命周期(五) - 销毁阶段
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Bean的生命周期(四) - 初始化阶段
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring ComponentScan
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Events
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring IOC 基础篇
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring IOC 总结
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring IOC 进阶篇
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring IOC容器的生命周期
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Resource
  • Java FrameWorks
    • Spring
      • Spring MVC
        • DispatcherServlet的初始化原理
  • Java FrameWorks
    • Spring
      • Spring MVC
        • DispatcherServlet的核心工作原理
  • Java FrameWorks
    • Spring
      • Spring MVC
        • WebMvc的架构设计与组件功能解析
  • Java FrameWorks
    • Spring
      • Spring Security
        • Spring Boot 2 + Spring Security 5 + JWT 的单页应用 Restful 解决方案
  • Java FrameWorks
    • Spring
      • Spring Security
        • Spring Security Oauth
  • Java FrameWorks
    • Spring
      • Spring Security
        • Spring Security
  • Java FrameWorks
    • Spring
      • Spring WebFlux
        • DispatcherHandler的工作原理(传统方式)
  • Java FrameWorks
    • Spring
      • Spring WebFlux
        • DispatcherHandler的工作原理(函数式端点)
  • Java FrameWorks
    • Spring
      • Spring WebFlux
        • WebFlux的自动装配
  • Java FrameWorks
    • Spring
      • Spring WebFlux
        • 快速了解响应式编程与Reactive
  • Java FrameWorks
    • Spring
      • Spring WebFlux
        • 快速使用WebFlux
  • 分布式
    • 协调服务
      • Zookeeper
        • Zookeeper - 客户端之 Curator
  • 分布式
    • 协调服务
      • Zookeeper
        • 详解分布式协调服务 ZooKeeper
  • 分布式
    • 协调服务
      • etcd
        • 高可用分布式存储 etcd 的实现原理
  • 数据库
    • Database Version Control
      • Flyway
        • Database Migrations with Flyway
  • 数据库
    • Database Version Control
      • Flyway
        • How Flyway works
  • 数据库
    • Database Version Control
      • Flyway
        • Rolling Back Migrations with Flyway
  • 数据库
    • Database Version Control
      • Flyway
        • The meaning of the concept of checksums
  • 数据库
    • Database Version Control
      • Liquibase
        • Introduction to Liquibase Rollback
  • 数据库
    • Database Version Control
      • Liquibase
        • LiquiBase中文学习指南
  • 数据库
    • Database Version Control
      • Liquibase
        • Use Liquibase to Safely Evolve Your Database Schema
  • 系统设计
    • 流量控制
      • RateLimiter
        • Guava Rate Limiter实现分析
  • 系统设计
    • 流量控制
      • Sentinel
        • Sentinel 与 Hystrix 的对比
  • 系统设计
    • 流量控制
      • Sentinel
        • Sentinel工作主流程
  • 系统设计
    • 流量控制
      • 算法
        • 分布式服务限流实战
  • 系统设计
    • 解决方案
      • 秒杀系统
        • 如何设计一个秒杀系统
  • 系统设计
    • 解决方案
      • 红包系统
        • 微信高并发资金交易系统设计方案--百亿红包背后的技术支撑
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 什么是预排序遍历树算法(MPTT,Modified Preorder Tree Traversal)
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 加密算法
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 推荐系统算法
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • linkerd
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 查找算法
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 缓存淘汰算法中的LRU和LFU
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 负载均衡算法
  • 计算机基础
    • 数据结构与算法
      • 分布式算法
        • 分布式算法 - Paxos算法
  • 计算机基础
    • 数据结构与算法
      • 分布式算法
        • 分布式算法 - Raft算法
  • 计算机基础
    • 数据结构与算法
      • 分布式算法
        • 分布式算法 - Snowflake算法
  • 计算机基础
    • 数据结构与算法
      • 分布式算法
        • 分布式算法 - ZAB算法
  • 计算机基础
    • 数据结构与算法
      • 分布式算法
        • 分布式算法 - 一致性Hash算法
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - Bitmap & Bloom Filter
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - Map & Reduce
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - Trie树/数据库/倒排索引
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - 分治/hash/排序
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - 双层桶划分
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - 外(磁盘文件)排序
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - 布隆过滤器
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理算法
  • 计算机基础
    • 数据结构与算法
      • 字符串匹配算法
        • 字符串匹配 - 文本预处理:后缀树(Suffix Tree)
  • 计算机基础
    • 数据结构与算法
      • 字符串匹配算法
        • 字符串匹配 - 模式预处理:BM 算法 (Boyer-Moore)
  • 计算机基础
    • 数据结构与算法
      • 字符串匹配算法
        • 字符串匹配 - 模式预处理:KMP 算法(Knuth-Morris-Pratt)
  • 计算机基础
    • 数据结构与算法
      • 字符串匹配算法
        • 字符串匹配 - 模式预处理:朴素算法(Naive)(暴力破解)
  • 计算机基础
    • 数据结构与算法
      • 字符串匹配算法
        • 字符串匹配
  • 计算机基础
    • 数据结构与算法
      • 常用算法
        • 分支限界算法
  • 计算机基础
    • 数据结构与算法
      • 常用算法
        • 分治算法
  • 计算机基础
    • 数据结构与算法
      • 常用算法
        • 动态规划算法
  • 计算机基础
    • 数据结构与算法
      • 常用算法
        • 回溯算法
  • 计算机基础
    • 数据结构与算法
      • 常用算法
        • 贪心算法
  • 计算机基础
    • 数据结构与算法
      • 排序算法
        • 十大排序算法
  • 计算机基础
    • 数据结构与算法
      • 排序算法
        • 图解排序算法(一)之3种简单排序(选择,冒泡,直接插入)
  • 计算机基础
    • 数据结构与算法
      • 排序算法
        • 图解排序算法(三)之堆排序
  • 计算机基础
    • 数据结构与算法
      • 排序算法
        • 图解排序算法(二)之希尔排序
  • 计算机基础
    • 数据结构与算法
      • 排序算法
        • 图解排序算法(四)之归并排序
  • 计算机基础
    • 数据结构与算法
      • 数据结构
        • 树的高度和深度
  • 计算机基础
    • 数据结构与算法
      • 数据结构
        • 红黑树深入剖析及Java实现
  • 计算机基础
    • 数据结构与算法
      • 数据结构
        • 线性结构 - Hash
  • 计算机基础
    • 数据结构与算法
      • 数据结构
        • 线性结构 - 数组、链表、栈、队列
  • 计算机基础
    • 数据结构与算法
      • 数据结构
        • 逻辑结构 - 树
  • 运维&测试
    • 测试
      • Spock
        • Groovy 简明教程
  • 运维&测试
    • 测试
      • Spock
        • Spock 官方文档
  • 运维&测试
    • 测试
      • Spock
        • Spock单元测试框架介绍以及在美团优选的实践
  • 运维&测试
    • 测试
      • TDD
        • TDD 实践 - FizzFuzzWhizz(一)
  • 运维&测试
    • 测试
      • TDD
        • TDD 实践 - FizzFuzzWhizz(三)
  • 运维&测试
    • 测试
      • TDD
        • TDD 实践 - FizzFuzzWhizz(二)
  • 运维&测试
    • 测试
      • TDD
        • 测试驱动开发(TDD)- 原理篇
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Nacos
          • Nacos 服务注册的原理
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Nacos
          • Nacos 配置中心原理分析
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Seata
          • 服务调用过程
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Seata
          • Spring Cloud Bus
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Seata
          • Spring Cloud Consul
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Seata
          • Spring Cloud Stream
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Sentinel
          • Sentinel 与 Hystrix 的对比
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Sentinel
          • Sentinel
  • 微服务
    • Spring Cloud
      • Spring Cloud Netflix
        • Hystrix
          • How Hystrix Works
  • 微服务
    • Spring Cloud
      • Spring Cloud Netflix
        • Hystrix
          • Hystrix
  • 微服务
    • Spring Cloud
      • Spring Cloud Netflix
        • Hystrix
          • Hystrix原理与实战
  • 微服务
    • Spring Cloud
      • Spring Cloud Netflix
        • Hystrix
          • Spring Cloud Hystrix基本原理
由 GitBook 提供支持
在本页
  • 1. 算法简介
  • 2. 算法图例
  • 3. 参考

这有帮助吗?

  1. 计算机基础
  2. 数据结构与算法
  3. 字符串匹配算法

字符串匹配 - 模式预处理:KMP 算法(Knuth-Morris-Pratt)

上一页字符串匹配算法下一页计算机基础

最后更新于2年前

这有帮助吗?

[TOC]

Knuth-Morris-Pratt算法(简称KMP)是最常用的字符串匹配算法之一。

1. 算法简介

如下算法解释主要来源于这里,但是通常很难阅读完全,我推荐你直接进入下一节 图例解释部分。

我们来观察一下朴素的字符串匹配算法的操作过程。如下图(a)中所描述,在模式 P = ababaca 和文本 T 的匹配过程中,模板的一个特定位移 s,q = 5 个字符已经匹配成功,但模式 P 的第 6 个字符不能与相应的文本字符匹配。

2021-02-19-IIDPMY

此时,q 个字符已经匹配成功的信息确定了相应的文本字符,而知道这 q 个文本字符,就使我们能够立即确定某些位移是非法的。例如上图(a)中,我们可以判断位移 s+1 是非法的,因为模式 P 的第一个字符 a 将与模式的第二个字符 b 匹配的文本字符进行匹配,显然是不匹配的。而图(b)中则显示了位移 s’ = s+2 处,使模式 P 的前三个字符和相应的三个文本字符对齐后必定会匹配。KMP 算法的基本思路就是设法利用这些已知信息,不要把 "搜索位置" 移回已经比较过的位置,而是继续把它向后面移,这样就提高了匹配效率。

The basic idea behind KMP’s algorithm is: whenever we detect a mismatch (after some matches), we already know some of the characters in the text (since they matched the pattern characters prior to the mismatch). We take advantage of this information to avoid matching the characters that we know will anyway match.

已知模式 P[1..q] 与文本 T[s+1..s+q] 匹配,那么满足 P[1..k] = T[s’+1..s’+k] 其中 s’+k = s+q 的最小位移 s’ > s 是多少?这样的位移 s’ 是大于 s 的但未必非法的第一个位移,因为已知 T[s+1..s+q] 。在最好的情况下有 s’ = s+q,因此立刻能排除掉位移 s+1, s+2 .. s+q-1。在任何情况下,对于新的位移 s’,无需把 P 的前 k 个字符与 T 中相应的字符进行比较,因为它们肯定匹配。

可以用模式 P 与其自身进行比较,以预先计算出这些必要的信息。例如上图(c)中所示,由于 T[s’+1..s’+k] 是文本中已经知道的部分,所以它是字符串 Pq 的一个后缀。

此处我们引入模式的前缀函数 π(Pai),π 包含有模式与其自身的位移进行匹配的信息。这些信息可用于避免在朴素的字符串匹配算法中,对无用位移进行测试。

π[q] = max {k : k < q and Pk ⊐ Pq}

π[q] 代表当前字符之前的字符串中,最长的共同前缀后缀的长度。(π[q] is the length of the longest prefix of P that is a proper suffix of Pq.)

下图给出了关于模式 P = ababababca 的完整前缀函数 π,可称为部分匹配表(Partial Match Table)。

计算过程:

  • π[1] = 0,a 仅一个字符,前缀和后缀为空集,共有元素最大长度为 0;

  • π[2] = 0,ab 的前缀 a,后缀 b,不匹配,共有元素最大长度为 0;

  • π[3] = 1,aba,前缀 a ab,后缀 ba a,共有元素最大长度为 1;

  • π[4] = 2,abab,前缀 a ab aba,后缀 bab ab b,共有元素最大长度为 2;

  • π[5] = 3,ababa,前缀 a ab aba abab,后缀 baba aba ba a,共有元素最大长度为 3;

  • π[6] = 4,ababab,前缀 a ab aba abab ababa,后缀 babab abab bab ab b,共有元素最大长度为 4;

  • π[7] = 5,abababa,前缀 a ab aba abab ababa ababab,后缀 bababa ababa baba aba ba a,共有元素最大长度为 5;

  • π[8] = 6,abababab,前缀 .. ababab ..,后缀 .. ababab ..,共有元素最大长度为 6;

  • π[9] = 0,ababababc,前缀和后缀不匹配,共有元素最大长度为 0;

  • π[10] = 1,ababababca,前缀 .. a ..,后缀 .. a ..,共有元素最大长度为 1;

KMP 算法 KMP-MATCHER 中通过调用 COMPUTE-PREFIX-FUNCTION 函数来计算部分匹配表。

KMP-MATCHER(T, P)
n ← length[T]
m ← length[P]
π ← COMPUTE-PREFIX-FUNCTION(P)
q ← 0                          //Number of characters matched.
for i ← 1 to n                 //Scan the text from left to right.
    do while q > 0 and P[q + 1] ≠ T[i]
            do q ← π[q]        //Next character does not match.
        if P[q + 1] = T[i]
            then q ← q + 1     //Next character matches.
        if q = m               //Is all of P matched?
            then print "Pattern occurs with shift" i - m
            q ← π[q]           //Look for the next match.
COMPUTE-PREFIX-FUNCTION(P)
m ← length[P]
π[1] ← 0
k ← 0
for q ← 2 to m
     do while k > 0 and P[k + 1] ≠ P[q]
            do k ← π[k]
        if P[k + 1] = P[q]
           then k ← k + 1
        π[q] ← k
return π

预处理过程 COMPUTE-PREFIX-FUNCTION 的运行时间为 Θ(m),KMP-MATCHER 的匹配时间为 Θ(n)。

相比较于 NAIVE-STRING-MATCHER,KMP-MATCHER 的主要优化点就是在当确定字符不匹配时对于 pattern 的位移。

NAIVE-STRING-MATCHER 的位移效果是:文本向后移一位,模式从头开始。

s = s - j + 1;
j = 0;

KMP-MATCHER 首先对模式做了获取共同前缀后缀最大长度的预处理操作,位移过程是先将模式向后移 partial_match_length - table[partial_match_length - 1],然后再判断是否匹配。这样通过对已匹配字符串的已知信息的利用,可以有效节省比较数量。

    if (j != 0)
        j = lps[j - 1];
    else
        s++;

下面描述了当发现字符 j 与 c 不匹配时的位移效果。

    // partial_match_length - table[partial_match_length - 1]
    rrababababjjjjjiiooorababababcauuu
      ||||||||-
      ababababca
    // 8-6=2
    rrababababjjjjjiiooorababababcauuu
      xx||||||-
        ababababca
    // 6-4=2
    rrababababjjjjjiiooorababababcauuu
        xx||||-
          ababababca
    // 4-2=2
    rrababababjjjjjiiooorababababcauuu
          xx||-
            ababababca
    // 2-0=2
    rrababababjjjjjiiooorababababcauuu
            xx-
              ababababca

综上可知,KMP 算法的主要特点是:

  • 需要对模式字符串做预处理;

  • 预处理阶段需要额外的 O(m) 空间和复杂度;

  • 匹配阶段与字符集的大小无关;

  • 匹配阶段至多执行 2n - 1 次字符比较;

  • 对模式中字符的比较顺序时从左到右;

2. 算法图例

下面,我用自己的语言,试图写一篇比较好懂的KMP算法解释。

首先,字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符,进行比较。因为B与A不匹配,所以搜索词后移一位。

因为B与A不匹配,搜索词再往后移。

就这样,直到字符串有一个字符,与搜索词的第一个字符相同为止。

接着比较字符串和搜索词的下一个字符,还是相同。

直到字符串有一个字符,与搜索词对应的字符不相同为止。

这时,最自然的反应是,将搜索词整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把"搜索位置"移到已经比较过的位置,重比一遍。

一个基本事实是,当空格与D不匹配时,你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是,设法利用这个已知信息,不要把"搜索位置"移回已经比较过的位置,继续把它向后移,这样就提高了效率。

怎么做到这一点呢?可以针对搜索词,算出一张《部分匹配表》(Partial Match Table)。这张表是如何产生的,后面再介绍,这里只要会用就可以了。

已知空格与D不匹配时,前面六个字符"ABCDAB"是匹配的。查表可知,最后一个匹配字符B对应的"部分匹配值"为2,因此按照下面的公式算出向后移动的位数:

移动位数 = 已匹配的字符数 - 对应的部分匹配值

因为 6 - 2 等于4,所以将搜索词向后移动4位。

因为空格与C不匹配,搜索词还要继续往后移。这时,已匹配的字符数为2("AB"),对应的"部分匹配值"为0。所以,移动位数 = 2 - 0,结果为 2,于是将搜索词向后移2位。

因为空格与A不匹配,继续后移一位。

逐位比较,直到发现C与D不匹配。于是,移动位数 = 6 - 2,继续将搜索词向后移动4位。

逐位比较,直到搜索词的最后一位,发现完全匹配,于是搜索完成。如果还要继续搜索(即找出全部匹配),移动位数 = 7 - 0,再将搜索词向后移动7位,这里就不再重复了。

下面介绍《部分匹配表》是如何产生的。

首先,要了解两个概念:"前缀"和"后缀"。 "前缀"指除了最后一个字符以外,一个字符串的全部头部组合;"后缀"指除了第一个字符以外,一个字符串的全部尾部组合。

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例,

  - "A"的前缀和后缀都为空集,共有元素的长度为0;

  - "AB"的前缀为[A],后缀为[B],共有元素的长度为0;

  - "ABC"的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;

  - "ABCD"的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;

  - "ABCDA"的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为"A",长度为1;

  - "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为"AB",长度为2;

  - "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。

"部分匹配"的实质是,有时候,字符串头部和尾部会有重复。比如,"ABCDAB"之中有两个"AB",那么它的"部分匹配值"就是2("AB"的长度)。搜索词移动的时候,第一个"AB"向后移动4位(字符串长度-部分匹配值),就可以来到第二个"AB"的位置。

3. 参考

  • http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/

  • https://www.cnblogs.com/gaochundong/p/string_matching.html#kmp_string_matching_algorithm

  • http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

  • https://www.pdai.tech/md/algorithm/alg-domain-char-match-kmp.html

2021-02-19-Qp3rDx

如下是阮一峰根据的文章总结的图例。

2021-02-19-IWGe7h
2021-02-19-cRBybA
2021-02-19-Hjqn5U
2021-02-19-cZYYDt
2021-02-19-R2LnQa
2021-02-19-H3KhkV
2021-02-19-ZGULM0
2021-02-19-Z4zdoV
2021-02-19-zkp4pn
2021-02-19-qC27Fv
2021-02-19-5vMYkm
2021-02-19-K4bjdb
2021-02-19-rQ4smU
2021-02-19-Rz9kH5
2021-02-19-7DNpng
2021-02-19-JGGvsc
Jake Boxer (opens new window)