KMP算法-蒲公英云

KMP算法

时间紧迫直接贴代码，后期有时间再补上

#include <iostream>
#include <fstream>
#include <string>
#include <ostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <unordered_set>
#include "cstring"
#define N 1001
using namespace std;
typedef struct MyString { 
    char *ch;
    int length;
} MyString;
int getStringLength(const char array[]) { 
    int length = 0;
    if (array == nullptr) { 
        return length;
    }
    while (array[length] != '\0') { 
        length++;
    }
    return length;
}
/** * 获取next数组的内容 * @param substr 模式串 * @param next next数组 */
void getNext(MyString substr, int next[]) { 
    int j = 1;
    int t = 0;
    next[1] = 0;
    while (j < substr.length) { 
        if (t == 0 || substr.ch[j] == substr.ch[t]) { 
            next[j + 1] = t + 1;
            t++;
            j++;
        } else { 
            t = next[t];
        }
    }
}
/* P 为模式串，下标从 0 开始 */
void GetNext(string P, int next[]) { 
    int p_len = P.size();
    int i = 0;   // P 的下标
    int j = -1;
    next[0] = -1;
    while (i < p_len - 1) { 
        if (j == -1 || P[i] == P[j]) { 
            i++;
            j++;
            next[i] = j;
        } else
            j = next[j];
    }
}
int KMP(MyString str, MyString substr, const int next[]) { 
    int i = 1;
    int j = 1;
    while (i <= str.length && j <= substr.length) { 
        if (j == 0 || str.ch[i] == substr.ch[j]) { 
            i++;
            j++;
        } else { 
            j = next[j];
        }
    }
    if (j > substr.length) { 
        return (i - substr.length);
    } else { 
        return 0;
    }
}
int main() { 
    MyString str, substr;
    str.ch = " abcabaaabaabcac";
    substr.ch = " abaabcac";
// substr.ch = " aabbcabbaa";
    str.length = getStringLength(str.ch);
    substr.length = getStringLength(substr.ch);
    int *next = static_cast<int *>(malloc((substr.length) * sizeof(int)));
    getNext(substr, next);
    for (int i = 1; i < substr.length; i++) { 
        cout << next[i] << " ";
    }
    cout << endl;
    cout << str.length << " " << substr.length << endl;
    int kmp = KMP(str, substr, next);
    cout << kmp << endl;
    return 0;
}