# 14075: 【原4075】KMP

### 题目描述

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

ababcabc

bcab

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;
}