2013 年机考试题

1、字符串匹配

KMP 算法

#include <iostream>
#include<vector>

using namespace std;

vector<int> getNext(string p, int n) {
    vector<int> next(n, -1);
    int j = 0, k = -1;
    while (j < n - 1) {
        if (k == -1 || p[j] == p[k]) {
            k++; j++;
            next[j] = (p[j] != p[k]) ? k : next[k];
        }
        else {
            k = next[k];
        }
    }
    return next;
}

int kmp(string s, string p) {
    int m = s.size(), n = p.size();
    vector<int> next = getNext(p, n);
    int i = 0, j = 0;
    while (i < m && j < n) {
        if (j == -1 || s[i] == p[j]) {
            i++; j++;
        }
        else {
            j = next[j];
        }
    }
    return (j == n) ? i - j : -1;
}
int main() {
    string M, P;
    cin >> M >> P;
    cout << kmp(M, P) << endl;
    return 0;
}

英语题就不写了