Skip to content

14075: 【原4075】KMP

题目

题目描述

author: MapleInWind 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4075

Description

给你两个0-base的字符串A、B，请输出B在A中第一次出现的位置。 * |A| <= 10^6 * |B| <= 10^5

Input Format

两行，第一行表示字符串A，第二行表示字符串B。 保证A中包含B。

Output Format

一行，表示B在A中第一次出现的位置。

Sample Input

ababcabc

bcab

Sample Output

3

ligongzzz's solution 

#include "iostream"
#include "cstring"
using namespace std;

char A[1000009], B[100009];

int KMP(char* source, char* destination) {
    int len_source = strlen(source),
        len_destination = strlen(destination);

    //int same_num = 0;
    int* same_nums = new int[len_destination] {0};
    for (int i = 0, j = 0; i < len_source;) {
        //每一位比较
        if (source[i] == destination[j]) {
            //判断是否重复
            if (j > 0 && destination[j] == destination[same_nums[j - 1]]) {
                same_nums[j] = same_nums[j - 1] + 1;
            }
            else if (j > 0) {
                same_nums[j] = 0;
                if (destination[j] == destination[0])
                    ++same_nums[j];
            }
            //移动
            ++i, ++j;
            //判断
            if (j == len_destination)
                return i - len_destination;
        }
        else {
            if (j == 0)
                ++i, j = 0;
            else
                j = same_nums[j - 1];
        }
    }
    //匹配失败
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> A >> B;
    cout << KMP(A, B);

    return 0;
}

Neight99's solution 

#include <cstring>
#include <iostream>

using namespace std;

const int aMax = 1e7 + 100;
const int bMax = 1e6 + 100;

char A[aMax] = {0}, B[bMax] = {0};
int bNext[aMax] = {0};

void makeNext(char *, int *);

int kmp(char *, char *, int *);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int ans;
    cin >> A >> B;

    ans = kmp(A, B, bNext);

    cout << ans;

    return 0;
}

int kmp(char *A, char *B, int *bNext) {
    int lenA, lenB;

    lenA = strlen(A);
    lenB = strlen(B);

    makeNext(B, bNext);

    for (int i = 0, j = 0; i < lenA; i++) {
        while (j > 0 && B[j] != A[i]) {
            j = bNext[j - 1];
        }
        if (B[j] == A[i]) {
            j++;
        }
        if (j == lenB) {
            return i - lenB + 1;
        }
    }
    return -1;
}

void makeNext(char *B, int *bNext) {
    int lenB = strlen(B);
    bNext[0] = 0;

    for (int i = 1, j = 0; i < lenB; i++) {
        while (j > 0 && B[i] != B[j]) {
            j = bNext[j - 1];
        }
        if (B[i] == B[j]) {
            j++;
        }
        bNext[i] = j;
    }
}

q4x3's solution 

/**
 * kmp板子
 **/
#include <iostream>
#include <cstring>
using namespace std;

int nxt[100233];
char txt[1000233], pat[100233];

void cal_nxt(int len) {
    //nxt[0]初始化为-1，-1表示不存在相同的最大前缀和最大后缀
    nxt[0] = -1;
    //k初始化为-1
    int k = -1;
    for (int i = 1; i <= len - 1; ++ i) {
        //如果下一个不同，那么k就变成nxt[k]，注意nxt[k]是小于k的，无论k取任何值
        while (k > -1 && pat[k + 1] != pat[i]) {
            k = nxt[k];//往前回溯
        }
        //如果相同，k++
        if (pat[k + 1] == pat[i]) {
            ++ k;
        }
        //把算的k的值（就是相同的最大前缀和最大后缀长）赋给nxt[i]
        nxt[i] = k;
    }
}

int kmp(int tlen, int plen) {
    int k = -1;
    for (int i = 0; i < tlen; ++ i)
    {
        //pat和txt不匹配，且k > -1（表示pat和txt有部分匹配）
        while (k > -1 && pat[k + 1] != txt[i])
            //往前回溯
            k = nxt[k];
        if (pat[k + 1] == txt[i]) ++ k;
        //说明k移动到pat的最末端
        if (k == plen - 1) return i - plen + 1;//返回相应的位置
    }
    return -1;
}

int main() {
    scanf("%s%s", txt, pat);
    int plen = strlen(pat), tlen = strlen(txt);
    cal_nxt(plen);
    cout << kmp(tlen, plen) << endl;
}

victrid's solution 

#include <cstring>
#include <iostream>
using namespace std;

inline bool n_strcmp(char* c1, char* c2, int digit) {
    while (digit--) {
        if (c2[digit] != c1[digit])
            return false;
    }
    return true;
}
inline int p_strcmp(char* c1, char* c2, int* partial, int digit) {
    if (c2[0] != c1[0])
        return 1;
    for (int i = 1; i < digit; i++) {
        if (c2[i] != c1[i]) {
            //0...i-1 are valid
            return i - partial[i - 1];
        }
    }
    return 0;
}
inline int partial(char* c1, int digit) {
    int ans = 0;
    for (int i = 1; i < digit; i++) {
        if (n_strcmp(c1, c1 + digit - i, i))
            ans = i;
    }
    return ans;
}
inline int* construct_partial(char* c1, int digit) {
    int* prefix = new int[digit]();
    for (int i = 1; i < digit; i++) {
        if (c1[i] == c1[prefix[i - 1]])
            prefix[i] = prefix[i - 1] + 1;
        else {
            int j = i - 1;
            while (prefix[j] > 0 && c1[prefix[j]] != c1[i])
                j = prefix[j] - 1;
            if (prefix[j] > 0)
                prefix[i] = prefix[j] + 1;
            else {
                prefix[i] = (c1[i] == c1[0]);
            }
        }
    }
    return prefix;
}
int kmp_strstr(char* heystack, char* needle) {
    int needlelen   = strlen(needle);
    int heystacklen = strlen(heystack);
    if (needlelen == 0)
        return 0;
    if (heystacklen == 0)
        return -1;
    int* partial = construct_partial(needle, needlelen);
    int ndigit = 0, hdigit = 0;
    while (hdigit < heystacklen) {
        while (needle[ndigit] == heystack[hdigit] && hdigit < heystacklen && ndigit < needlelen) {
            ++ndigit;
            ++hdigit;
        }
        if (ndigit == needlelen) {
            return hdigit - needlelen;
        }
        if (hdigit == heystacklen) {
            return -1;
        } else {
            if (ndigit == 0) {
                hdigit++;
                continue;
            }
            //Here you should not repeat comparisons you've already done.
            ndigit = partial[ndigit - 1];
        }
    }
    return -1;
}
char heys[1000002];
char nedl[100002];
int main() {
    cin.getline(heys, 1000001);
    cin.getline(nedl, 100001);
    printf("%d", kmp_strstr(heys, nedl));
    return 0;
}

yyong119's solution 

#include <cstdio>
#include <cstring>
using namespace std;
#define MAX_A 1000010
#define MAX_B 100010
char a[MAX_A], b[MAX_B];
int c[MAX_B];

int main() {

    scanf("%s", &a[0]);
    scanf("%s", &b[0]);
    int len_a = strlen(a), len_b = strlen(b);
    c[0] = -1;
    int i = 0, j = -1;
    while (i < len_b)
        if (j == -1 || b[i] == b[j])
            c[++i] = ++j;
        else
            j = c[j];

    i = j = 0;
    while (i < len_a && j < len_b)
        if (j == -1 || a[i] == b[j]) {
            ++i; ++j;
        }
        else
            j = c[j];
    printf("%d\n", i -  j);
    return 0;
}