Java教程

数据结构与算法-朴素匹配/KMP匹配

本文主要是介绍数据结构与算法-朴素匹配/KMP匹配,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
  • 条件:无

  • 题目:无

  • 原理:无

  • 代码:

    /*
    * 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();
    }
    
    
这篇关于数据结构与算法-朴素匹配/KMP匹配的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!