字符串匹配

问题地址 https://www.acwing.com/problem/content/description/833/

由于ACMer选手在比赛中总是记不住KMP算法，特此记录一下使用哈希字符串来代替KMP算法，唯一的缺陷就是害怕出题人卡哈希值(131、13331)

KMP算法

kmp next数组(坐标1开始)

import java.io.*;
import java.util.*;
import java.lang.*;
import java.math.*;

public class Main {

    Scanner sin = new Scanner(System.in);
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer cin = new StreamTokenizer(in);
    PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));

    final int N = 100010, mod = (int) (1e9 + 7), inf = 0x3f3f3f3f;

    int nextInt() throws Exception {
        cin.nextToken();
        return (int) cin.nval;
    }

    String next() throws Exception {
        cin.nextToken();
        return cin.sval;
    }

    int n, m;
    String x, s;
    int[] next = new int[N];

    void kmp() {
        int i = 1, j = 0;
        next[1] = 0;
        while (i <= n) {
            if (j == 0 || x.charAt(i) == x.charAt(j))
                next[++i] = ++j;
            else
                j = next[j];
        }
    }

    void solve() throws Exception {
        n = Integer.parseInt(in.readLine());
        x = in.readLine();
        m = Integer.parseInt(in.readLine());
        s = in.readLine();
        x = ' ' + x;
        s = ' ' + s;

        kmp();

        int i = 1, j = 1;
        while (i <= m) {
            if (j == 0 || s.charAt(i) == x.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
            if (j == n + 1) {
                cout.print(i - j + " ");
                j = next[j];
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Main cmd = new Main();
        cmd.solve();
        cmd.cout.close();
    }
}

Hash字符串

import java.io.*;
import java.util.*;
import java.lang.*;
import java.math.*;

public class Main {

    Scanner sin = new Scanner(System.in);
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer cin = new StreamTokenizer(in);
    PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));

    final int N = 100010, mod = (int)(1e9+7), inf = 0x3f3f3f3f;

    int nextInt() throws Exception {
        cin.nextToken();
        return (int) cin.nval;
    }

    String next() throws Exception {
        cin.nextToken();
        return cin.sval;
    }

    int n, m;
    String S, P;

    long base = 131;
    long[] p = new long[N * 10];
    long[] hp = new long[N];
    long[] hs = new long[N * 10];

    void init() {
        p[0] = 1;
        for (int i = 1; i <= Math.max(n, m); i ++) {
            if (i <= n) hp[i] = hp[i - 1] * base + P.charAt(i);
            if (i <= m) hs[i] = hs[i - 1] * base + S.charAt(i);
            p[i] = p[i - 1] * base;
        }
    }

    long hash(int l, int r) {
        return hs[r] - hs[l - 1] * p[r - l + 1];
    }

    void solve() throws Exception {

        n = Integer.parseInt(in.readLine());
        P = " " + in.readLine();

        m = Integer.parseInt(in.readLine());
        S = " " + in.readLine();

        init();

        for (int i = 1; n - 1 + i <= m; i ++) {
            if (hp[n] == hash(i, i + n - 1))
                cout.print(i - 1 + " ");
        }
    }

    public static void main(String[] args) throws Exception {
        Main cmd = new Main();
        cmd.solve();
        cmd.cout.close();
    }
}