条件：无

题目：无

原理：无

代码：

/*
* Author: Moota
* Copyright: Moota
* Description: Written by Moota  
*/
#include <iostream>  //cin,cout
#include <iomanip>  //fixed<<setprecision(2)
#include <algorithm>  //sort
#include <map>
#include <queue>
#include <stack>
#include <deque>  //双端队列，头可插，尾可插
#include <string>
#include <cstring>
#include <cmath> //sqrt,abs
#include <fstream>  //file
#include <ctime>
#include <climits> //数值极限
//(double)clock() / CLOCKS_PER_SEC <= 1 限制1s跑完程序
using namespace std;

class Solver {
public:
    Solver() {
        //取消和c输出输入的同步，加快读取
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        //誓死捍卫c++的风格
    }

public:
    void SaveCpp(string name) const {
        fstream input;
        fstream output;
        input.open("moota.cpp", ios::in);
        output.open(name.c_str(), ios::out);
        char c = 'O';
        while (!input.eof()) {
            input.get(c);
            output << c;
        }
        input.close();
        output.close();
    }

protected:
    virtual void BeginPlay() {
    };

    virtual void Playing() {
    };

    virtual void EndPlay() {
    };
public:
    void Play() {
        BeginPlay();
        Playing();
        EndPlay();
    }
};

class SpecialSolver : public Solver {
public:
    typedef long long int lld;
    typedef unsigned long long int ulld;
    static const lld MAX = static_cast<lld>(1e4);
    static const lld INF = static_cast<lld>(1e18);
private:
    string text, pattern;
    int kmp[MAX];
private:
    //朴素匹配
    void Normal() {
        const int aSize = text.size() - 1;
        const int bSize = pattern.size() - 1;
        for (int i = 1; i <= aSize; ++i) {
            int k = i;
            for (int j = 1; j <= bSize; ++j) {
                if (text[k] != pattern[j]) {
                    break;
                }
                else {
                    ++k;
                    if (j == bSize) {
                        cout << i << " ";
                    }
                }
            }
        }
    }

    //KMP数组

    void GetKMP() {
        kmp[0] = 0;
        //简单的认为一个字符不具有前后缀。
        kmp[1] = 0;
        //len：和自身匹配的字符串的下标。
        //len:也是最长的相同前后缀长度。
        //kmp[len]：到len位置为止（包括len）最大的相同前后缀长度
        int len = 0;
        const int aSize = pattern.size() - 1;
        for (int i = 2; i <= aSize; ++i) {
            //失配后，本来嘛，最大长度要直接回到0，
            //聪明的KMP知道这一段完全匹配，虽然失配了
            //但是1-j这段字符串有相同的前后缀，
            //所以跳到0不如跳到最长前缀的结束的那里。
            //比如：
            //abcabefg
            //abcabg
            //pattern[i]=e，pattern[len+1]=g时失配
            //一看 kmp[len]等于 2,
            //那么回去 pattern[len]=b，pattern[len+1]=c
            //这样只要比较 pattern[i]=e和 pattern[len+1]=c
            //不用从头比较了，为什么？
            //因为此时的最大前后缀
            //text前缀（ab）=pattern后缀(ab)，前后缀相等，无需比较。
            while (len > 0 && pattern[i] != pattern[len + 1]) {
                len = kmp[len];
            }
            //len+1 表示想要扩展，即将扩展的地方相等，就可以扩展
            if (pattern[i] == pattern[len + 1]) {
                ++len;
                kmp[i] = len;
            }
        }
    }

    //KMP 匹配
    void DoKMP() {
        int len = 0;
        //此时文本串就不是自身了
        const int aSize = text.size() - 1;
        const int bSize = pattern.size() - 1;
        //现在是匹配文本串，每一位都要匹配，所以从1开始。
        for (int i = 1; i <= aSize; ++i) {
            while (len > 0 && text[i] != pattern[len + 1]) {
                len = kmp[len];
            }
            if (text[i] == pattern[len + 1]) {
                ++len;
                if (len == bSize) {
                    cout << i - bSize + 1 << " ";
                    len = kmp[len];
                }
            }
        }
    }

protected:
    virtual void BeginPlay() override {
        Solver::BeginPlay();
        //注意修改文件名称
        //SaveCpp("KMP匹配.cpp");
        cin >> text >> pattern;
        text = " " + text;
        pattern = " " + pattern;
    };

    virtual void Playing() override {
        Solver::Playing();
        //abcabcabc abc
        cout << "\n朴素匹配：";
        Normal();
        cout << "\nKMP匹配：";
        GetKMP();
        DoKMP();
    };

    virtual void EndPlay() override {
        Solver::EndPlay();
    };
};

SpecialSolver specialSolver;

int main() {
    specialSolver.Play();
}