查漏补缺第十二期(网易实习三面)

前言

目前正在出一个查漏补缺专题系列教程, 篇幅会较多, 喜欢的话，给个关注❤️ ~

本专题主要以Java语言为主, 好了, 废话不多说直接开整吧~

Spring中bean的生命周期

在Spring框架中，Bean的生命周期可以被分为多个阶段，包括实例化、属性赋值、初始化、销毁等。下面是Spring中Bean的生命周期的详细过程：

1. 实例化：当Spring容器启动时，会根据配置文件或注解等方式来创建Bean的实例。这个阶段是通过调用Bean的构造函数来完成的。

2. 属性赋值：在实例化完成后，Spring容器会根据配置文件或注解等方式来设置Bean的属性。这可以通过setter方法进行属性注入，或者使用字段注入。

3. 初始化前回调方法：在属性赋值完成后，Spring容器会调用Bean的初始化前回调方法（如果有的话）。这些方法可以实现InitializingBean接口的afterPropertiesSet()方法，或者使用@PostConstruct注解进行标记。

4. 自定义初始化方法：在初始化前回调方法执行完毕后，Spring容器会调用Bean的自定义初始化方法（如果有的话）。这些方法是由开发人员自己定义的，并在配置文件或注解中进行指定。

5. 初始化后回调方法：在自定义初始化方法执行完毕后，Spring容器会调用Bean的初始化后回调方法（如果有的话）。这些方法可以实现InitializingBean接口的afterPropertiesSet()方法，或者使用@PostConstruct注解进行标记。

6. 使用Bean：在初始化完成后，Bean可以被应用程序使用。它们可以被注入到其他Bean中，或者通过Spring容器获取并使用。

7. 销毁前回调方法：当Spring容器关闭时，或者从容器中移除Bean时，会调用Bean的销毁前回调方法（如果有的话）。这些方法可以实现DisposableBean接口的destroy()方法，或者使用@PreDestroy注解进行标记。

8. 自定义销毁方法：在销毁前回调方法执行完毕后，Spring容器会调用Bean的自定义销毁方法（如果有的话）。这些方法是由开发人员自己定义的，并在配置文件或注解中进行指定。

需要注意的是，不是所有的Bean都需要定义初始化和销毁方法，这是可选的。如果Bean没有定义这些方法，它们的生命周期将仅限于实例化、属性赋值和使用阶段。

通过理解Spring中Bean的生命周期，可以在需要时执行一些特定的操作，例如在初始化时执行一些初始化逻辑或资源的分配，并在销毁时释放这些资源。这为开发人员提供了更大的灵活性和控制权。

Mysql binlog日志监听具体怎么实现

使用mysql-binlog-connector-java可以实现对MySQL Binlog日志的监听。这是一个开源的Java库，它提供了与MySQL的Binlog日志进行交互的功能。

下面是使用mysql-binlog-connector-java库进行MySQL Binlog日志监听的一般步骤：

1. 引入依赖：在你的Java项目中，需要添加mysql-binlog-connector-java的依赖。

<dependency>
    <groupId>mysql</groupId>
    <artifactId>mysql-connector-java</artifactId>
    <version>8.0.26</version>
</dependency>
<dependency>
    <groupId>mysql</groupId>
    <artifactId>mysql-connector-java</artifactId>
    <version>8.0.26</version>
</dependency>
<dependency>
    <groupId>mysql</groupId>
    <artifactId>mysql-connector-java</artifactId>
    <version>8.0.26</version>
</dependency>

2. 创建连接：使用mysql-connector-java库创建与MySQL数据库的连接。

import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.SQLException;
Connection connection = DriverManager.getConnection("jdbc:mysql://localhost:3306/mydatabase", "username", "password");
import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.SQLException;


Connection connection = DriverManager.getConnection("jdbc:mysql://localhost:3306/mydatabase", "username", "password");
import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.SQLException;


Connection connection = DriverManager.getConnection("jdbc:mysql://localhost:3306/mydatabase", "username", "password");

3. 配置Binlog监听器：创建一个BinaryLogClient对象并配置相应的监听器。

import com.github.shyiko.mysql.binlog.BinaryLogClient;
import com.github.shyiko.mysql.binlog.event.EventData;
import com.github.shyiko.mysql.binlog.event.EventType;
import com.github.shyiko.mysql.binlog.event.deserialization.EventDeserializer;
BinaryLogClient client = new BinaryLogClient("localhost", 3306, "username", "password");
EventDeserializer eventDeserializer = new EventDeserializer();
// 设置事件反序列化器的一些选项（可选）
eventDeserializer.setCompatibilityMode(EventDeserializer.CompatibilityMode.DATE_AND_TIME_AS_LONG);
client.setEventDeserializer(eventDeserializer);
client.registerEventListener(event -> {
    EventData eventData = event.getData();
    EventType eventType = event.getHeader().getEventType();
    // 处理不同的事件类型
    if (eventType == EventType.WRITE_ROWS) {
        // 处理插入数据事件
        // eventData提供了事件相关的数据，可以解析出具体的操作内容
    } else if (eventType == EventType.UPDATE_ROWS) {
        // 处理更新数据事件
    } else if (eventType == EventType.DELETE_ROWS) {
        // 处理删除数据事件
    }
    // ...
});
import com.github.shyiko.mysql.binlog.BinaryLogClient;
import com.github.shyiko.mysql.binlog.event.EventData;
import com.github.shyiko.mysql.binlog.event.EventType;
import com.github.shyiko.mysql.binlog.event.deserialization.EventDeserializer;


BinaryLogClient client = new BinaryLogClient("localhost", 3306, "username", "password");
EventDeserializer eventDeserializer = new EventDeserializer();
// 设置事件反序列化器的一些选项（可选）
eventDeserializer.setCompatibilityMode(EventDeserializer.CompatibilityMode.DATE_AND_TIME_AS_LONG);
client.setEventDeserializer(eventDeserializer);



client.registerEventListener(event -> {
    EventData eventData = event.getData();
    EventType eventType = event.getHeader().getEventType();
    // 处理不同的事件类型
    if (eventType == EventType.WRITE_ROWS) {
        // 处理插入数据事件
        // eventData提供了事件相关的数据，可以解析出具体的操作内容
    } else if (eventType == EventType.UPDATE_ROWS) {
        // 处理更新数据事件
    } else if (eventType == EventType.DELETE_ROWS) {
        // 处理删除数据事件
    }
    // ...
});
import com.github.shyiko.mysql.binlog.BinaryLogClient;
import com.github.shyiko.mysql.binlog.event.EventData;
import com.github.shyiko.mysql.binlog.event.EventType;
import com.github.shyiko.mysql.binlog.event.deserialization.EventDeserializer;


BinaryLogClient client = new BinaryLogClient("localhost", 3306, "username", "password");
EventDeserializer eventDeserializer = new EventDeserializer();
// 设置事件反序列化器的一些选项（可选）
eventDeserializer.setCompatibilityMode(EventDeserializer.CompatibilityMode.DATE_AND_TIME_AS_LONG);
client.setEventDeserializer(eventDeserializer);



client.registerEventListener(event -> {
    EventData eventData = event.getData();
    EventType eventType = event.getHeader().getEventType();
    // 处理不同的事件类型
    if (eventType == EventType.WRITE_ROWS) {
        // 处理插入数据事件
        // eventData提供了事件相关的数据，可以解析出具体的操作内容
    } else if (eventType == EventType.UPDATE_ROWS) {
        // 处理更新数据事件
    } else if (eventType == EventType.DELETE_ROWS) {
        // 处理删除数据事件
    }
    // ...
});

4. 启动监听：通过调用connect()方法启动Binlog监听。

client.connect();
client.connect();
client.connect();

监听器现在会接收到MySQL Binlog日志中发生的事件，并根据事件类型执行相应的操作。

5. 关闭连接：在不需要监听时，可以通过调用disconnect()方法关闭与MySQL数据库的连接。

client.disconnect();
client.disconnect();
client.disconnect();

请注意，上述代码示例仅提供了基本的监听和处理Binlog事件的框架，你可能需要根据实际需求进行更详细的处理和业务逻辑。此外，你还需要确保MySQL服务器启用了二进制日志（Binary Log）功能，以便进行Binlog日志的监听。

如何保证redis和mysql数据一致性,有哪些方法?

要保证Redis和MySQL之间的数据一致性，需要考虑数据的读取、更新和同步的过程。

1. 数据写入：
   • 当有数据要写入MySQL时，首先将数据写入MySQL数据库。
   • 接着，通过数据库的触发器或其他方式，将写入操作异步地发送到Redis，更新对应的缓存数据。

// 示例代码（Java + MySQL）
// 将数据写入MySQL数据库
public void writeToMySQL(Data data) {
    // 执行插入或更新操作
    String sql = "INSERT INTO my_table (id, name, value) VALUES (?, ?, ?) ON DUPLICATE KEY UPDATE name = VALUES(name), value = VALUES(value)";
    try (Connection connection = DriverManager.getConnection("jdbc:mysql://localhost:3306/mydatabase", "username", "password");
        PreparedStatement statement = connection.prepareStatement(sql)) {
        statement.setInt(1, data.getId());
        statement.setString(2, data.getName());
        statement.setString(3, data.getValue());
        statement.executeUpdate();
    } catch (SQLException e) {
        // 处理异常
    }
    // 异步将写入操作发送到Redis
    asyncUpdateRedisCache(data);
}
// 示例代码（Java + MySQL）
// 将数据写入MySQL数据库
public void writeToMySQL(Data data) {
    // 执行插入或更新操作
    String sql = "INSERT INTO my_table (id, name, value) VALUES (?, ?, ?) ON DUPLICATE KEY UPDATE name = VALUES(name), value = VALUES(value)";
    try (Connection connection = DriverManager.getConnection("jdbc:mysql://localhost:3306/mydatabase", "username", "password");
        PreparedStatement statement = connection.prepareStatement(sql)) {
        statement.setInt(1, data.getId());
        statement.setString(2, data.getName());
        statement.setString(3, data.getValue());
        statement.executeUpdate();
    } catch (SQLException e) {
        // 处理异常
    }

    // 异步将写入操作发送到Redis
    asyncUpdateRedisCache(data);
}
// 示例代码（Java + MySQL）
// 将数据写入MySQL数据库
public void writeToMySQL(Data data) {
    // 执行插入或更新操作
    String sql = "INSERT INTO my_table (id, name, value) VALUES (?, ?, ?) ON DUPLICATE KEY UPDATE name = VALUES(name), value = VALUES(value)";
    try (Connection connection = DriverManager.getConnection("jdbc:mysql://localhost:3306/mydatabase", "username", "password");
        PreparedStatement statement = connection.prepareStatement(sql)) {
        statement.setInt(1, data.getId());
        statement.setString(2, data.getName());
        statement.setString(3, data.getValue());
        statement.executeUpdate();
    } catch (SQLException e) {
        // 处理异常
    }

    // 异步将写入操作发送到Redis
    asyncUpdateRedisCache(data);
}

2. 数据读取：
   • 当需要读取数据时，首先从Redis缓存中查询数据。
   • 如果缓存中存在数据，则直接返回。
   • 如果缓存中不存在数据，则从MySQL数据库读取数据，并将数据存入Redis缓存中。

// 示例代码（Java + Redis）
// 从Redis缓存中读取数据
public Data readFromRedis(int id) {
    try (Jedis jedis = jedisPool.getResource()) {
        String cacheKey = "data:" + id;
        String cachedData = jedis.get(cacheKey);
        if (cachedData != null) {
            // 缓存命中，直接返回数据
            return parseDataFromJson(cachedData);
        } else {
            // 缓存未命中，从MySQL数据库读取数据
            Data data = readFromMySQL(id);
            if (data != null) {
                // 将数据存入Redis缓存
                jedis.set(cacheKey, toJson(data));
            }
            return data;
        }
    }
}
// 从MySQL数据库读取数据
private Data readFromMySQL(int id) {
    // 执行查询操作，获取数据
    String sql = "SELECT id, name, value FROM my_table WHERE id = ?";
    try (Connection connection = DriverManager.getConnection("jdbc:mysql://localhost:3306/mydatabase", "username", "password");
        PreparedStatement statement = connection.prepareStatement(sql)) {
        statement.setInt(1, id);
        try (ResultSet resultSet = statement.executeQuery()) {
            if (resultSet.next()) {
                // 解析并返回数据
                Data data = new Data();
                data.setId(resultSet.getInt("id"));
                data.setName(resultSet.getString("name"));
                data.setValue(resultSet.getString("value"));
                return data;
            }
        }
    } catch (SQLException e) {
        // 处理异常
    }
    return null;
}
// 示例代码（Java + Redis）
// 从Redis缓存中读取数据
public Data readFromRedis(int id) {
    try (Jedis jedis = jedisPool.getResource()) {
        String cacheKey = "data:" + id;
        String cachedData = jedis.get(cacheKey);
        if (cachedData != null) {
            // 缓存命中，直接返回数据
            return parseDataFromJson(cachedData);
        } else {
            // 缓存未命中，从MySQL数据库读取数据
            Data data = readFromMySQL(id);
            if (data != null) {
                // 将数据存入Redis缓存
                jedis.set(cacheKey, toJson(data));
            }
            return data;
        }
    }
}


// 从MySQL数据库读取数据
private Data readFromMySQL(int id) {
    // 执行查询操作，获取数据
    String sql = "SELECT id, name, value FROM my_table WHERE id = ?";
    try (Connection connection = DriverManager.getConnection("jdbc:mysql://localhost:3306/mydatabase", "username", "password");
        PreparedStatement statement = connection.prepareStatement(sql)) {
        statement.setInt(1, id);
        try (ResultSet resultSet = statement.executeQuery()) {
            if (resultSet.next()) {
                // 解析并返回数据
                Data data = new Data();
                data.setId(resultSet.getInt("id"));
                data.setName(resultSet.getString("name"));
                data.setValue(resultSet.getString("value"));
                return data;
            }
        }
    } catch (SQLException e) {
        // 处理异常
    }
    return null;
}
// 示例代码（Java + Redis）
// 从Redis缓存中读取数据
public Data readFromRedis(int id) {
    try (Jedis jedis = jedisPool.getResource()) {
        String cacheKey = "data:" + id;
        String cachedData = jedis.get(cacheKey);
        if (cachedData != null) {
            // 缓存命中，直接返回数据
            return parseDataFromJson(cachedData);
        } else {
            // 缓存未命中，从MySQL数据库读取数据
            Data data = readFromMySQL(id);
            if (data != null) {
                // 将数据存入Redis缓存
                jedis.set(cacheKey, toJson(data));
            }
            return data;
        }
    }
}


// 从MySQL数据库读取数据
private Data readFromMySQL(int id) {
    // 执行查询操作，获取数据
    String sql = "SELECT id, name, value FROM my_table WHERE id = ?";
    try (Connection connection = DriverManager.getConnection("jdbc:mysql://localhost:3306/mydatabase", "username", "password");
        PreparedStatement statement = connection.prepareStatement(sql)) {
        statement.setInt(1, id);
        try (ResultSet resultSet = statement.executeQuery()) {
            if (resultSet.next()) {
                // 解析并返回数据
                Data data = new Data();
                data.setId(resultSet.getInt("id"));
                data.setName(resultSet.getString("name"));
                data.setValue(resultSet.getString("value"));
                return data;
            }
        }
    } catch (SQLException e) {
        // 处理异常
    }
    return null;
}

3. 数据更新同步：
   • 在MySQL中进行数据更新时，确保同步更新Redis缓存。

可以通过数据库的触发器或其他方式，在数据更新之后，异步地发送更新操作到Redis，使Redis中的缓存数据保持与MySQL一致。

// 示例代码（MySQL触发器）
CREATE TRIGGER my_table_after_update
AFTER UPDATE ON my_table
FOR EACH ROW
BEGIN
    DECLARE jsonString VARCHAR(255);
    SET jsonString = CONCAT('{"id":', NEW.id, ',"name":"', NEW.name, '","value":"', NEW.value, '"}');
    CALL sys_exec('redis-cli SET data:' + CAST(NEW.id AS CHAR) + ' ' + jsonString);
END;
// 示例代码（MySQL触发器）
CREATE TRIGGER my_table_after_update
AFTER UPDATE ON my_table
FOR EACH ROW
BEGIN
    DECLARE jsonString VARCHAR(255);
    SET jsonString = CONCAT('{"id":', NEW.id, ',"name":"', NEW.name, '","value":"', NEW.value, '"}');
    CALL sys_exec('redis-cli SET data:' + CAST(NEW.id AS CHAR) + ' ' + jsonString);
END;
// 示例代码（MySQL触发器）
CREATE TRIGGER my_table_after_update
AFTER UPDATE ON my_table
FOR EACH ROW
BEGIN
    DECLARE jsonString VARCHAR(255);
    SET jsonString = CONCAT('{"id":', NEW.id, ',"name":"', NEW.name, '","value":"', NEW.value, '"}');
    CALL sys_exec('redis-cli SET data:' + CAST(NEW.id AS CHAR) + ' ' + jsonString);
END;

这只是一种常见的实现方案，具体的实现方式可以根据实际需求进行调整。需要注意的是，异步更新Redis缓存的操作需要额外的机制，例如使用消息队列或异步任务来处理。

MD5加密的算法是怎么实现的，能讲讲原理吗

MD5（Message Digest Algorithm 5）是一种常用的消息摘要算法，用于将任意长度的数据生成固定长度（128位）的哈希值。

MD5算法的基本原理：

1. 数据填充：对待加密数据进行填充，使其长度满足一定要求，一般是64位的倍数。
2. 初始化：将一些预定义的常量赋值给四个32位寄存器（A、B、C、D）。
3. 处理数据：将填充后的数据划分为若干个512位的数据块，并对每个数据块进行处理。
   • 对每个数据块进行四轮循环处理，每轮循环都有16个步骤。
   • 每轮循环中，根据当前数据块中的数据和上一轮循环中的寄存器值进行一系列的位运算和逻辑运算。
   • 每轮循环的结果都会更新寄存器的值。
4. 结果输出：将最后一轮循环处理的寄存器值按顺序连接起来，得到128位的哈希值。

import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
public class MD5Example {
    public static void main(String[] args) {
        String input = "Hello, World!";
        String md5Hash = getMD5Hash(input);
        System.out.println("MD5 Hash: " + md5Hash);
    }
    public static String getMD5Hash(String input) {
        try {
            // 创建MD5摘要算法实例
            MessageDigest md = MessageDigest.getInstance("MD5");
            // 计算哈希值
            byte[] hashBytes = md.digest(input.getBytes());
            // 转换为十六进制表示
            BigInteger hashNumber = new BigInteger(1, hashBytes);
            String hashString = hashNumber.toString(16);
            // 如果哈希值的长度不足32位，前面补0
            while (hashString.length() < 32) {
                hashString = "0" + hashString;
            }
            return hashString;
        } catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
        }
        return null;
    }
}
import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;


public class MD5Example {
    public static void main(String[] args) {
        String input = "Hello, World!";
        String md5Hash = getMD5Hash(input);
        System.out.println("MD5 Hash: " + md5Hash);
    }




    public static String getMD5Hash(String input) {
        try {
            // 创建MD5摘要算法实例
            MessageDigest md = MessageDigest.getInstance("MD5");
            // 计算哈希值
            byte[] hashBytes = md.digest(input.getBytes());
            // 转换为十六进制表示
            BigInteger hashNumber = new BigInteger(1, hashBytes);
            String hashString = hashNumber.toString(16);
            // 如果哈希值的长度不足32位，前面补0
            while (hashString.length() < 32) {
                hashString = "0" + hashString;
            }
            return hashString;
        } catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
        }
        return null;
    }
}
import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;


public class MD5Example {
    public static void main(String[] args) {
        String input = "Hello, World!";
        String md5Hash = getMD5Hash(input);
        System.out.println("MD5 Hash: " + md5Hash);
    }




    public static String getMD5Hash(String input) {
        try {
            // 创建MD5摘要算法实例
            MessageDigest md = MessageDigest.getInstance("MD5");
            // 计算哈希值
            byte[] hashBytes = md.digest(input.getBytes());
            // 转换为十六进制表示
            BigInteger hashNumber = new BigInteger(1, hashBytes);
            String hashString = hashNumber.toString(16);
            // 如果哈希值的长度不足32位，前面补0
            while (hashString.length() < 32) {
                hashString = "0" + hashString;
            }
            return hashString;
        } catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
        }
        return null;
    }
}

在示例代码中，我们使用java.security.MessageDigest类提供的API来计算MD5哈希值。首先创建了一个MessageDigest实例，并指定算法为”MD5″。然后将待加密的数据转换为字节数组，并通过digest()方法计算哈希值。最后，将哈希值转换为十六进制字符串表示，并补足长度为32位。

需要注意的是，MD5算法是一种单向散列函数，它不可逆。因此，通过MD5哈希值无法还原原始数据。此外，MD5算法目前已经被认为不是足够安全，因为它存在碰撞（不同数据生成相同哈希值）的风险。在实际应用中，更推荐使用更安全的哈希算法，如SHA-256等。

找出字符串中第一个匹配项的下标（力扣28题）

给你两个字符串 haystack 和needle，请你在 haystack 字符串中找出needle字符串的第一个匹配项的下标（下标从 0 开始）。如果needle不是 haystack 的一部分，则返回 -1 。

KMP (Knuth-Morris-Pratt)算法实现：

public class KMPSearch {
    public static void main(String[] args) {
        String text = "Hello, World!";
        String pattern = "Hells";
        int index = kmpSearch(text, pattern);
        System.out.println("First match index: " + index);
        // -1
    }
    public static int kmpSearch(String text, String pattern) {
        if (text == null || pattern == null || text.isEmpty() || pattern.isEmpty()) {
            return -1;
        }
        int[] lps = computeLPSArray(pattern);
        int i = 0; // text中的索引
        int j = 0; // pattern中的索引
        while (i < text.length()) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                if (j == pattern.length()) {
                    return i - j; // 匹配成功，返回第一个匹配项的下标
                }
            } else {
                if (j != 0) {
                    j = lps[j - 1]; // 回溯到最长公共前后缀的下一个位置
                } else {
                    i++; // 没有找到匹配项，继续在text中前进
                }
            }
        }
        return -1; // 没有找到匹配项
    }
    private static int[] computeLPSArray(String pattern) {
        int[] lps = new int[pattern.length()];
        int len = 0; // 最长公共前后缀的长度
        int i = 1;
        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1]; // 回溯到前一个位置继续匹配
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }
}
public class KMPSearch {
    public static void main(String[] args) {
        String text = "Hello, World!";
        String pattern = "Hells";


        int index = kmpSearch(text, pattern);
        System.out.println("First match index: " + index);

        // -1
    }




    public static int kmpSearch(String text, String pattern) {
        if (text == null || pattern == null || text.isEmpty() || pattern.isEmpty()) {
            return -1;
        }

        int[] lps = computeLPSArray(pattern);

        int i = 0; // text中的索引
        int j = 0; // pattern中的索引


        while (i < text.length()) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;

                if (j == pattern.length()) {
                    return i - j; // 匹配成功，返回第一个匹配项的下标
                }
            } else {
                if (j != 0) {
                    j = lps[j - 1]; // 回溯到最长公共前后缀的下一个位置
                } else {
                    i++; // 没有找到匹配项，继续在text中前进
                }
            }
        }

        return -1; // 没有找到匹配项
    }

    private static int[] computeLPSArray(String pattern) {
        int[] lps = new int[pattern.length()];
        int len = 0; // 最长公共前后缀的长度
        int i = 1;

        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1]; // 回溯到前一个位置继续匹配
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }

        return lps;
    }
}
public class KMPSearch {
    public static void main(String[] args) {
        String text = "Hello, World!";
        String pattern = "Hells";


        int index = kmpSearch(text, pattern);
        System.out.println("First match index: " + index);

        // -1
    }




    public static int kmpSearch(String text, String pattern) {
        if (text == null || pattern == null || text.isEmpty() || pattern.isEmpty()) {
            return -1;
        }

        int[] lps = computeLPSArray(pattern);

        int i = 0; // text中的索引
        int j = 0; // pattern中的索引


        while (i < text.length()) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;

                if (j == pattern.length()) {
                    return i - j; // 匹配成功，返回第一个匹配项的下标
                }
            } else {
                if (j != 0) {
                    j = lps[j - 1]; // 回溯到最长公共前后缀的下一个位置
                } else {
                    i++; // 没有找到匹配项，继续在text中前进
                }
            }
        }

        return -1; // 没有找到匹配项
    }

    private static int[] computeLPSArray(String pattern) {
        int[] lps = new int[pattern.length()];
        int len = 0; // 最长公共前后缀的长度
        int i = 1;

        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1]; // 回溯到前一个位置继续匹配
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }

        return lps;
    }
}

KMP算法的时间复杂度为O(n + m)，其中n是文本字符串的长度，m是模式字符串的长度。

在KMP算法中，首先需要计算模式字符串的最长公共前后缀（Longest Proper Prefix which is also Suffix，简称LPS）数组，该过程的时间复杂度为O(m)。

接下来，在搜索过程中，我们使用两个指针i和j分别指向文本字符串和模式字符串的当前位置。在每一次比较过程中，i和j要么都向前移动一步，要么只有j回溯到LPS数组的值。由于每个位置的字符最多被比较一次，因此总共进行n次比较。

因此，总的时间复杂度为O(n + m)。

KMP算法通过利用模式字符串的信息，避免了不必要的回溯，提高了字符串匹配的效率。相比于朴素的字符串匹配算法，其时间复杂度大大减少。

结束语

大家可以针对自己薄弱的地方进行复习, 然后多总结，形成自己的理解，不要去背~

本着把自己知道的都告诉大家，如果本文对您有所帮助，点赞+关注鼓励一下呗~

相关文章

• 查漏补缺第一期(Redis相关)
• 查漏补缺第二期(synchronized & 锁升级)
• 查漏补缺第三期(分布式事务相关)
• 查漏补缺第四期(Mysql相关)
• 查漏补缺第五期(HashMap & ConcurrentHashMap)
• 查漏补缺第六期(京东一面)
• 查漏补缺第七期(美团到店一面)
• 查漏补缺第八期(阿里一面)
• 查漏补缺第九期(阿里二面)
• 查漏补缺第十期(网易实习一面)
• 查漏补缺第十一期(网易实习二面)

项目源码(源码已更新 欢迎star⭐️)

• java-interview-all: https://github.com/qiuChengleiy/java-interview-all

往期设计模式相关文章

• 一起来学设计模式之认识设计模式
• 一起来学设计模式之单例模式
• 一起来学设计模式之工厂模式
• 一起来学设计模式之建造者模式
• 一起来学设计模式之原型模式
• 一起来学设计模式之适配器模式
• 一起来学设计模式之桥接模式
• 一起来学设计模式之组合模式
• 一起来学设计模式之装饰器模式
• 一起来学设计模式之外观模式
• 一起来学设计模式之享元模式
• 一起来学设计模式之代理模式
• 一起来学设计模式之责任链模式
• 一起来学设计模式之命令模式
• 一起来学设计模式之解释器模式
• 一起来学设计模式之迭代器模式
• 一起来学设计模式之中介者模式
• 一起来学设计模式之备忘录模式
• 一起来学设计模式之观察者模式
• 一起来学设计模式之状态模式
• 一起来学设计模式之策略模式
• 一起来学设计模式之模板方法模式
• 一起来学设计模式之访问者模式
• 一起来学设计模式之依赖注入模式

设计模式项目源码(源码已更新 欢迎star⭐️)

• java-design-mode-all: https://github.com/qiuChengleiy/java-design-mode-all

Kafka 专题学习

• 一起来学kafka之Kafka集群搭建
• 一起来学kafka之整合SpringBoot基本使用
• 一起来学kafka之整合SpringBoot深入使用(一)
• 一起来学kafka之整合SpringBoot深入使用(二)
• 一起来学kafka之整合SpringBoot深入使用(三)

项目源码(源码已更新 欢迎star⭐️)

• springboot-kafka-all: https://github.com/qiuChengleiy/springboot-kafka-all

ElasticSearch 专题学习

• 利用docker搭建es集群

• 一起来学ElasticSearch(一)

• 一起来学ElasticSearch(二)

• 一起来学ElasticSearch(三)

• 一起来学ElasticSearch(四)

• 一起来学ElasticSearch(五)

• 一起来学ElasticSearch(六)

• 一起来学ElasticSearch(七)

• 一起来学ElasticSearch(八)

• 一起来学ElasticSearch(九)

• 一起来学ElasticSearch(十)

• 一起来学ElasticSearch之整合SpringBoot(一)

• 一起来学ElasticSearch之整合SpringBoot(二)

• 一起来学ElasticSearch之整合SpringBoot(三)

项目源码(源码已更新 欢迎star⭐️)

• springboot-es-all: https://github.com/qiuChengleiy/springboot-es-all

往期并发编程内容推荐

• Java多线程专题之线程与进程概述
• Java多线程专题之线程类和接口入门
• Java多线程专题之进阶学习Thread(含源码分析)
• Java多线程专题之Callable、Future与FutureTask(含源码分析)
• 面试官: 有了解过线程组和线程优先级吗
• 面试官: 说一下线程的生命周期过程
• 面试官: 说一下线程间的通信
• 面试官: 说一下Java的共享内存模型
• 面试官: 有了解过指令重排吗，什么是happens-before
• 面试官: 有了解过volatile关键字吗 说说看
• 面试官: 有了解过Synchronized吗 说说看
• Java多线程专题之Lock锁的使用
• 面试官: 有了解过ReentrantLock的底层实现吗？说说看
• 面试官: 有了解过CAS和原子操作吗？说说看
• Java多线程专题之线程池的基本使用
• 面试官: 有了解过线程池的工作原理吗？说说看
• 面试官: 线程池是如何做到线程复用的？有了解过吗，说说看
• 面试官: 阻塞队列有了解过吗?说说看
• 面试官: 阻塞队列的底层实现有了解过吗? 说说看
• 面试官: 同步容器和并发容器有用过吗? 说说看
• 面试官: CopyOnWrite容器有了解过吗? 说说看
• 面试官: Semaphore在项目中有使用过吗？说说看(源码剖析)
• 面试官: Exchanger在项目中有使用过吗？说说看(源码剖析)
• 面试官: CountDownLatch有了解过吗？说说看(源码剖析)
• 面试官: CyclicBarrier有了解过吗？说说看(源码剖析)
• 面试官: Phaser有了解过吗？说说看
• 面试官: Fork/Join 有了解过吗？说说看（含源码分析）
• 面试官: Stream并行流有了解过吗？说说看

推荐 SpringBoot & SpringCloud (源码已更新 欢迎star⭐️)

• springboot-all https://github.com/qiuChengleiy/springboot-all.git

• SpringBoot系列教程合集

• 一起来学SpringCloud合集

• SpringCloud整合 Oauth2+Gateway+Jwt+Nacos 实现授权码模式的服务认证(一)

• SpringCloud整合 Oauth2+Gateway+Jwt+Nacos 实现授权码模式的服务认证(二)

博客(阅读体验较佳)

• 我的博客(阅读体验较佳)