小明的字符串(kmp)

骑猪看日落 2024-03-31 13:11 113阅读 0赞

#### 记录一道KMP的题目， ####

#### 这道题对于刚接触kmp的同学来说算是一道不错的题目了， ####

#### 能够帮助我们理解得更深刻... ####

题目：小明的字符串

#### 题目描述 ####

小明有两个字符串，分别为 S,T。

请你求出 TT 串的前缀在 S 串中出现的最长长度为多少。

#### 输入描述 ####

输入包含两行，每行包含一个字符串，分别表示 S,T。

1 < |S|,|T| < 10^6 ，保证 S,T 只包含小写字母。

#### 输出描述 ####

输出共 1 行，包含一个整数，表示答案。

#### 输入输出样例 ####

示例 1

输入

aabba

abb

输出

示例 2

输入

aabba

aba

输出

#### 运行限制 ####

*  最大运行时间：1s
 *  最大运行内存: 256M

import java.util.Scanner;
    
    
    public class Main {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            String str1 = scanner.nextLine();
            String str2 = scanner.nextLine();
            int[] next = kmpNext(str2);
            int temp;
            for (int i = str2.length(); i > 0; i--) {
                temp = kmpSearch(str1, str2.substring(0, i), next);
                if (temp != -1) {
                    System.out.println(temp);
                    break;
                }
            }
        }
    
        private static int kmpSearch(String str1, String str2, int[] next) {
            int j = 0;
            for (int i = 0; i < str1.length(); i++) {
                while (j > 0 && str1.charAt(i) != str2.charAt(j))
                    j = next[j - 1];
                if (str1.charAt(i) == str2.charAt(j))
                    j++;
                if (j == str2.length()) return str2.length();
            }
            return -1;
        }
    
        private static int[] kmpNext(String str2) {
            int[] next = new int[str2.length()];
            int j = 0;
            for (int i = 1; i < str2.length(); i++) {
                while (j > 0 && str2.charAt(i) != str2.charAt(j))
                    j = next[j - 1];
                if (str2.charAt(i) == str2.charAt(j))
                    j++;
                next[i] = j;
            }
            return next;
        }
    
    }