[Luogu-P3375] KMP字符串匹配

发表于 | 更新于 | 分类于 ， ，
本文字数： 7.3k

链接

\(\text{Luogu-P3375 KMP字符串匹配}\)

题意

  输入两个串\(s_1、s_2\)，求出\(s_2\)在\(s_1\)中所有出现的位置（匹配的开始位置），并输出子串的\(next\)数组的；

  数据范围：\(s_1\)长度为\(n\)，\(s_2\)长度为\(M\)，\(n\leq 1000000,m\leq 1000000\).

分析

  这是一个\(kmp\)的模板题；

  这里我用了\(Java\)来写，然而一直TLE，不知什么原因，最后发现了原因，在于String的使用；

  在\(ACM\)竞赛中需要特别注意Java中String及与其有关的一些函数；String是一个不可变的对象，每次对String进行修改时都等同于生成了一个新的String临时对象，如果需要经常对其修改，那么这是相当浪费时间的；

  在此题中，我使用了一个String.format()函数来控制格式的输出，这个函数会返回一个String，而我又在for里反复使用了它，所以会TLE；我试了仅仅使用String.format()输出了一个元素，是不会超时的，所以仅仅是\(O(1)\)的使用它是不会超时的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.io.*;  
import java.util.*;  
import java.lang.*;  

public class Main {  
    public static int [] next = new int[1000003];  
    public static int n, m;  
    public static void main(String[] args) {  
        Scanner input =new Scanner(new BufferedInputStream(System.in));  
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));  
        String s1 = input.nextLine(), s2 = input.nextLine();  
        n = s1.length();  
        m = s2.length();  
        kmp(s2);  
        for (int i = 1, j = 0; i <= n; i++) {  
            while (j > 0 && (j == m || s1.charAt(i - 1) != s2.charAt(j)))j = next[j];  
            if (s1.charAt(i - 1) == s2.charAt(j)) {  
                j++;  
            }  
            if (j == m) {  
                out.println(i - j + 1);  
                // 在s1中，和s2匹配的各串之间可以覆盖  
                j = next[j];  
                // j = 0 在s1中，和s2匹配的各串之间可以覆盖  
                // 即下一个匹配的串的开始位置，必须在上一个匹配的串的结束位置的后面  
            }  
        }  
        for (int i = 1; i <= m - 1; i++) {  
           out.print(next[i] + " ");  
        }  
        out.println(String.format("%d",next[m]));  
        out.flush();  
    }  
    public static void kmp(String s) {  
        next[1] = 0;  
        for (int i = 2, j = 0; i <= m; i++) {  
            while (j > 0 && s.charAt(i - 1) != s.charAt(j)) j = next[j];  
            if (s.charAt(i - 1) == s.charAt(j)) j++;  
            next[i] = j;  
        }  
    }  
}