KMP算法

时间限制: 1 Sec  内存限制: 128 MB

题目描述

学习KMP算法,给出主串和模式串,求模式串在主串的位置

输入

第一个输入t,表示有t个实例

第二行输入第1个实例的主串,第三行输入第1个实例的模式串

以此类推

输出

第一行输出第1个实例的模式串的next值

第二行输出第1个实例的匹配位置,位置从1开始计算,如果匹配成功输出位置,匹配失败输出0

以此类推

样例输入

3 qwertyuiop tyu aabbccdd ccc aaaabababac abac 

样例输出

-1 0 0  5 -1 0 1  0 -1 0 0 1  8 

提示

 为什么next值和课本的不一样???

解决方案

#include <iostream>
#include <string>
class MyString {
private:
    std::string mainStr; //串
    static void getNext(std::string p, int next[]) {
        next[0] = -1;
        next[1] = 0;
        int temp = 0;
        int L = p.length();
        for (int i = 2; i < L; ++i) { //从第二个字符开始,依次计算next的值
            while (temp > 0 && p[i - 1] != p[temp]) {
                temp = next[temp];
            }
            if (p[i - 1] == p[temp]) {
                temp++;
            }
            next[i] = temp;
        }
    };
    int KMPFind(std::string p, const int next[]) {
        int i = 0, j = 0;
        while (mainStr[i] != '\0' && p[j] != '\0') {
            if (mainStr[i] == p[j]) {
                ++i;
                ++j;
            } else {
                j = next[j];
            }
            if (j == -1) {
                ++i;
                ++j;
            }
        }
        if (p[j] == '\0') {
            return i - j;
        } else {
            return -1;
        }
    };
public:
    MyString(); //构造函数
    ~MyString(); //析构函数
    void setVal(const std::string &sp); //设定主串字符内容和长度
    int KMPFindSubstr(const std::string &p);
};
MyString::MyString() { //构造函数,定义对象并赋初始串值
    mainStr = "";
}
MyString::~MyString() { //析构函数
    mainStr = "";
}
void MyString::setVal(const std::string &sp) {
    mainStr = "";
    mainStr.assign(sp);
}
int MyString::KMPFindSubstr(const std::string &p) { //主串从pos开始查找子串p。找到返回p在主串开始的位置,否贼返回-1
    int L = p.length();
    int *next = new int[L];
    getNext(p, next);
    for (int j = 0; j < L; ++j) {
        std::cout << next[j] << ' ';
    }
    std::cout << std::endl;
    int v = KMPFind(p, next);
    delete[]next;
    return v;
}
int main() {
    size_t t;
    std::cin >> t;
    while (t--) {
        std::string mainStr, subStr;
        std::cin >> mainStr;
        std::cin >> subStr;
        MyString myString;
        myString.setVal(mainStr);
        std::cout << myString.KMPFindSubstr(subStr) + 1 << std::endl;
    }
}

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇