精华内容
下载资源
问答
  • 一、如何将中缀表达式转化为后缀表达式 在日常应用中,算术表达式中运算符总是出现在两个操作数之间,例如5*(7-23)+8/2,这种形式称为中缀表达式。计算一个中缀表达式需要知道运算符的优先级和结合...

    题目:输入一个中缀表达式,计算其结果。
    输入的前提假设:
    (1)只考虑+、-、*、/这四种运算符,中缀表达式中只有一种括号:();
    (2)输入的中缀表达式中只有整数,没有小数;
    (3)假定输入是合法的。

    一、如何将中缀表达式转化为后缀表达式

    在日常应用中,算术表达式中运算符总是出现在两个操作数之间,例如5*(7-23)+8/2,这种形式称为中缀表达式。计算一个中缀表达式需要知道运算符的优先级和结合性。乘除是高优先级,加减是低优先级,优先级相同时他们都是左结合的,也就是从左计算到右。有括号就要计算括号内的表达式。
    中缀表达式利于人的理解,但不便于计算机的处理。因此需要将中缀表达式转换成后缀表达式,以方便计算机处理。所谓后缀表达式就是将运算符放在运算数之后。后缀表达式也称为逆波兰表达式。
    比如:
    中缀表达式为: 1   +   (   2   −   3   )   ∗   4   +   4   /   2 1 + ( 2 - 3 ) * 4 + 4 / 2 1 + ( 2  3 )  4 + 4 / 2
    对应后缀表达式为: 1   2   3   −   4   ∗   +   4   2   /   + 1  2  3  -  4 *  +  4  2  /  + 1 2 3  4  + 4 2 / +
    如何将一个中缀表达式转化为后缀表达式?我们需要借助栈的力量,用它来存放运算符。算法流程如下:
    首先将各种运算符(包括括号)的优先级排列如下(数字越大,优先级越高):
    1:(
    2:+ -
    3:
    /
    4:)
    对输入的中缀表达式从左到右遍历:
    1)如果遇到数字,直接添加到后缀表达式末尾;
    2)如果遇到运算符+、-、*、/:
    先判断栈是否为空。若是,则直接将此运算符压入栈。若不是,则查看当前栈顶元素。若栈顶元素优先级大于或等于此操作符级别,则弹出栈顶元素,将栈顶元素添加到后缀表达式中,并继续进行上述判断。如果不满足上述判断或者栈为空,将这个运算符入栈。要注意的是,经过上述步骤,这个运算符最终一定会入栈。
    3)如果遇到括号:
    如果是左括号,直接入栈。如果是右括号,弹出栈中第一个左括号前所有的操作符,并将左括号弹出。(右括号别入栈)。
    4)字符串遍历结束后,如果栈不为空,则弹出栈中所有元素,将它们添加到后缀表达式的末尾,直到栈为空。

    二、计算后缀表达式

    后缀表达式的计算就相当简单了。准备一个数字栈。从左到右扫描后缀表达式,如果是数字,放入数字栈。如果是符号,从数字栈中弹出两个数字,第一个取出的数字为右运算数,第二个为左运算数,进行运算。然后将结果放进数字栈中。如此反复,直到读完整个表达式后,留在数字栈中的那个数字就是最终结果。

    三、代码如下:

    #include <bits/stdc++.h>
    using namespace std;
    int main(){
        map<char,int>p;
        p['('] = 1;
        p['+'] = 2; p['-'] = 2;
        p['*'] = 3; p['/'] = 3;
        p[')'] = 4;
        string s;
        ifstream cin("input.txt");
        while(cin >> s){
    
            //中缀转后缀
            vector<int>result;
            stack<char>op;
            int t = 0;
            for(int i = 0; i < s.size(); i++){
                if(isdigit(s[i])){
                    t = t * 10 + s[i] - '0';
                    if(i+1<s.size() && !isdigit(s[i+1])){
                        result.push_back(t);
                        t = 0;
                    }
                }
                else{
                    if(s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/'){
                        if(op.size() <= 0){
                            op.push(s[i]);
                        }else{
                            while(op.size() > 0 && p[op.top()] >= p[s[i]]){
                                result.push_back((int)op.top());
                                op.pop();
                            }
                            op.push(s[i]);
                        }
                    }
                    else if(s[i] == '('){
                        op.push(s[i]);
                    }else{
                        while(op.top() != '('){
                            result.push_back((int)op.top());
                            op.pop();
                        }
                        op.pop();
                    }
                }
            }
            while(op.size() > 0){
                result.push_back((int)op.top());
                op.pop();
            }
    //        for(auto i : result){
    //            if(i>=40)cerr<<(char)i<<" ";
    //            else
    //            cerr << i << " ";
    //        }
            //计算后缀式
            stack<int>sk;
            for(int i = 0; i < result.size(); i++){
                if(result[i] == '+' || result[i] == '-' || result[i] == '*' || result[i] == '/'){
                    int b = sk.top(); sk.pop();
                    int a = sk.top(); sk.pop();
                    int c;
                    if(result[i] == '+'){
                        c = a + b;
                    }else if(result[i] == '-'){
                        c = a - b;
                    }else if(result[i] == '*'){
                        c = a * b;
                    }else {
                        c = a / b;
                    }
                    sk.push(c);
                }else{
                    sk.push(result[i]);
                }
            }
            cout << sk.top() << endl;
        }
    }
    

    样例输入

    4+23-10/5#
    3
    (7-2)#
    2*3/2#

    样例输出

    8
    15
    3

    展开全文
  • 【C++】std::vector源码浅析

    千次阅读 2015-12-03 15:30:19
    std::vector是stl标准模板库中的一个序列容器,其源码实现有几个特点:(1)C++中include的标准头文件是没有“.h”后缀的,其实这是C++的一层包裹,内部实现还是在“.h”文件中完成的,以我们include的vector为例,...

    std::vector是stl标准模板库中的一个序列容器,其源码实现有几个特点:

    (1)C++中include的标准头文件是没有“.h”后缀的,其实这是C++的一层包裹,内部实现还是在“.h”文件中完成的,以我们include的vector为例,其中还会include一些真正的vector实现文件,如“stl_vector.h”。

    (2)vector的实现有一些内部使用的函数和数据类型,它们以下划线“_”开头。

    (3)vector是个模板类,继承自_Vector_base,_Vector_base是个struct,它有一个嵌套的struct为_Vector_impl,其中有三个关键的指针成员变量,_M_start,_M_finish,_M_end_of_storage,明白这三个变量对vector的理解很有帮助。

    (4)我们通常使用的vector接口,大部分是通过形如“_M_xxx”的内部函数实现的。

    (5)vector的操作符首先实现了判等“==”和小于“<”,其它的操作符都是基于这两个操作符实现的。

    (6)vector中有一些C++11引入的语法,可在源码中茶看得到。

    下面看一下源码中的“vector”和“stl_vector.h”都有什么内容。

    /* vector */
    
    //>头文件普遍都有的宏保护, 防止多重include
    //>GNU C++ Library, 即libstdc++.so, 而非libc++.so
    //>lib库名不同也就是GNU与标准C++的不同实现的区别
    #ifndef _GLIBCXX_VECTOR
    #define _GLIBCXX_VECTOR 1
    
    //>pragma预处理用法
    //>告诉GCC该位置下面的include为系统头文件
    //>不影响该位置上面的部分
    #pragma GCC system_header
    
    /* 从下面的include可以看出, 有多个不同类型的vector. */
    
    //>算法相关的模板函数
    #include <bits/stl_algobase.h>
    //>用于内存分配的模板类
    //>typedef了许多常见的数据类型
    #include <bits/allocator.h>
    //>非标准的对象创建/销毁的模板函数
    //>如_Construct/_Destroy
    #include <bits/stl_construct.h>
    //>操作原始内存的模板函数
    //>从头文件的名字就可以看出, 函数并不初始化内存
    #include <bits/stl_uninitialized.h>
    //>正宗的vector模版类
    #include <bits/stl_vector.h>
    //>vector模板类的特化版本
    //>用bool特化的vector模板, 即vector<bool>
    #include <bits/stl_bvector.h> 
    //>模板函数, 获取迭代器Iterator的begin/end
    #include <bits/range_access.h>
    
    //>tcc版vector
    #ifndef _GLIBCXX_EXPORT_TEMPLATE
    # include <bits/vector.tcc>
    #endif
    
    //>debug版vector
    #ifdef _GLIBCXX_DEBUG
    # include <debug/vector>
    #endif
    
    //>profile版vector
    #ifdef _GLIBCXX_PROFILE
    # include <profile/vector>
    #endif
    
    #endif /* _GLIBCXX_VECTOR */
    
    
    /* stl_vector.h */
    
    //>头文件普遍都有的宏保护
    #ifndef _STL_VECTOR_H
    #define _STL_VECTOR_H 1
    
    //>Iterator迭代器通用的函数, 如distance/advance/next/prev
    #include <bits/stl_iterator_base_funcs.h>
    
    //>异常控制的几个函数声明
    #include <bits/functexcept.h>
    
    //>一些精巧的宏定义,typedef了一些数据类型
    #include <bits/concept_check.h>
    
    //>__cplusplus C++版本
    #if __cplusplus >= 201103L
    //>initializer_list模板类
    //>C++11引入的, 初始化列表, 提供了迭代器
    #include <initializer_list>
    #endif
    
    //>_GLIBCXX_VISIBILIT在c++config.h中有定义
    //>简单来说即__attribute__((__visibility__("default")))
    //>这个是gcc __attribute__的用法
    //>详细定义如下
    /***********
    #define _GLIBCXX_HAVE_ATTRIBUTE_VISIBILITY 1
    
    #if _GLIBCXX_HAVE_ATTRIBUTE_VISIBILITY
    # define _GLIBCXX_VISIBILITY(V) __attribute__((__visibility__(#V)))
    #else
    # define _GLIBCXX_VISIBILITY(V) _GLIBCXX_PSEUDO_VISIBILITY(V)
    #endif
    
    #ifndef _GLIBCXX_PSEUDO_VISIBILITY
    # define _GLIBCXX_PSEUDO_VISIBILITY(V)
    #endif
    **********/
    namespace std _GLIBCXX_VISIBILITY(default)
    {
    //>_GLIBCXX_BEGIN_NAMESPACE_CONTAINER在c++config.h中有定义
    //>这里即一个空的宏定义
    //>详细定义如下
    /**********
    #if defined(_GLIBCXX_DEBUG) || defined(_GLIBCXX_PROFILE)
    # define _GLIBCXX_STD_C __cxx1998
    # define _GLIBCXX_BEGIN_NAMESPACE_CONTAINER \
        namespace _GLIBCXX_STD_C { _GLIBCXX_BEGIN_NAMESPACE_VERSION
    # define _GLIBCXX_END_NAMESPACE_CONTAINER \
        } _GLIBCXX_END_NAMESPACE_VERSION
    #endif
    
    #ifndef _GLIBCXX_STD_C
    # define _GLIBCXX_STD_C std
    #endif
    
    #ifndef _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
    # define _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
    #endif
    
    #ifndef _GLIBCXX_END_NAMESPACE_CONTAINER
    # define _GLIBCXX_END_NAMESPACE_CONTAINER
    #endif
    
    #define _GLIBCXX_INLINE_VERSION 0 
    
    #if _GLIBCXX_INLINE_VERSION
    # define _GLIBCXX_BEGIN_NAMESPACE_VERSION namespace __7 {
    # define _GLIBCXX_END_NAMESPACE_VERSION }
    #else
    # define _GLIBCXX_BEGIN_NAMESPACE_VERSION
    # define _GLIBCXX_END_NAMESPACE_VERSION
    #endif
    **********/
    _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
    
      //>_Vector_base为vector的基类, 模板类
      //>_Tp是个具体的类型
      //>_Alloc为内存分配器, 可参照std::allocator
      template<typename _Tp, typename _Alloc>
        struct _Vector_base
        {
          //>typedef定义类型的别名
          //>typename表示其后的内容是个类型, 否则会被当作普通字段
          //>__gnu_cxx名字空间中的__alloc_traits是allocator的统一接口
          //>_Tp_alloc_type定义的简单形式如下
          //>typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
          //>如果模板参数_Alloc为std::allocator的话, _Tp_alloc_type的定义如下
          //>typedef typename allocator<_Tp> _Tp_alloc_type;
          typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
            rebind<_Tp>::other _Tp_alloc_type;
          //>同上, pointer即typedef typename _Tp_alloc_type::pointer pointer;
          //>同上, 如果模板参数_Alloc为std::allocator的话, pointer将非常简单, 如下所示
          //>typedef typename _Tp* pointer;
          //>绕了一大圈, 其实很简单!
          typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer
            pointer;
    
          //>嵌套struct
          //>_Vector_base implementation
          struct _Vector_impl 
          : public _Tp_alloc_type
          {
            //>三个重要的指针成员变量, 贯穿于整个vector
            //>用集合的方法表示vector就是[_M_start, _M_finish)
            //>指向vector中第一个元素的地址
            pointer _M_start;
            //>指向vector中最后一个元素的下一个位置的地址
            pointer _M_finish;
            //>指向vector的容量的末地址
            pointer _M_end_of_storage;
    
            //>构造函数的两个版本
            //>初始化列表中调用了对应的基类构造函数
            //>初始化列表中初始化了各指针成员变量, 且初始化顺序与变量声明的顺序保持一致
            _Vector_impl()
            : _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0)
            { }
    
            _Vector_impl(_Tp_alloc_type const& __a)
            : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
            { }
    
    #if __cplusplus >= 201103L
            //>符号&&即rvalue, 右值引用, C++11引进的, 调用std::move
            //>符号&即lvalue, 传统的左值引用
            _Vector_impl(_Tp_alloc_type&& __a)
            : _Tp_alloc_type(std::move(__a)),
            _M_start(0), _M_finish(0), _M_end_of_storage(0)
            { }
    #endif
    
            //>数据交换, 参数类型为&, 直接调用了std::swap
            //>交换的是三个指针成员变量
            void _M_swap_data(_Vector_impl& __x)
            {
              std::swap(_M_start, __x._M_start);
              std::swap(_M_finish, __x._M_finish);
              std::swap(_M_end_of_storage, __x._M_end_of_storage);
            }
          }; //> struct _Vector_impl
    
        public:
          //>stl中多处使用了typedef, 目的就是让数据类型更加简单、具体
          typedef _Alloc allocator_type;
    
          //>非const版本与const版本的_M_get_Tp_allocator
          //>使用static_cast把子类指针转化为父类指针, 即up-cast, 类型安全
          //>_GLIBCXX_NOEXCEPT即异常相关的宏定义
          /**********
          #ifndef _GLIBCXX_NOEXCEPT
          # if __cplusplus >= 201103L
          #  define _GLIBCXX_NOEXCEPT noexcept
          # else
          #  define _GLIBCXX_NOEXCEPT
          # endif
          #endif
          **********/
          //>noexcept是C++11引进的, 即不抛出任何异常, 等价于throw()
          _Tp_alloc_type&
          _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
          { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
    
          const _Tp_alloc_type&
          _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
          { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
    
          //>获取allocator_type对象
          //>可理解为_Alloc<_Tp>类型的对象
          //>调用了某个版本的构造函数
          allocator_type
          get_allocator() const _GLIBCXX_NOEXCEPT
          { return allocator_type(_M_get_Tp_allocator()); }
    
          //>下面是几个版本的构造函数
          _Vector_base()
          : _M_impl() { }
    
          _Vector_base(const allocator_type& __a)
          : _M_impl(__a) { }
    
          //>参数__n指定了vector大小
          //>调用_M_create_storage分配内存
          _Vector_base(size_t __n)
          : _M_impl()
          { _M_create_storage(__n); }
    
          _Vector_base(size_t __n, const allocator_type& __a)
          : _M_impl(__a)
          { _M_create_storage(__n); }
    
    #if __cplusplus >= 201103L
          //>rvalue版本的几个构造函数
          _Vector_base(_Tp_alloc_type&& __a)
          : _M_impl(std::move(__a)) { }
    
          _Vector_base(_Vector_base&& __x)
          : _M_impl(std::move(__x._M_get_Tp_allocator()))
          { this->_M_impl._M_swap_data(__x._M_impl); }
    
          _Vector_base(_Vector_base&& __x, const allocator_type& __a)
          : _M_impl(__a)
          {
            if (__x.get_allocator() == __a)
              this->_M_impl._M_swap_data(__x._M_impl);
            else
            {
              size_t __n = __x._M_impl._M_finish - __x._M_impl._M_start;
              _M_create_storage(__n);
            }
          }
    #endif
    
          //>析构, 内存释放, 最终会调用到::operator delete操作符
          ~_Vector_base()
          { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage
                  - this->_M_impl._M_start); }
    
        public:
          //>成员变量类型为内嵌的struct, 一种简单的设计模式
          _Vector_impl _M_impl;
    
          //>内存分配, 最终会调用到::operator new操作符
          pointer
          _M_allocate(size_t __n)
          { return __n != 0 ? _M_impl.allocate(__n) : 0; }
    
          //>内存释放
          void
          _M_deallocate(pointer __p, size_t __n)
          {
            if (__p)
              _M_impl.deallocate(__p, __n);
          }
    
        private:
          //>私有的创建存储空间的函数
          //>调用上面的_M_Allocate来分配内存
          void
          _M_create_storage(size_t __n)
          {
            this->_M_impl._M_start = this->_M_allocate(__n);
            this->_M_impl._M_finish = this->_M_impl._M_start;
            this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
          }
        };
    
    
      //>真正的vector模板类, _Alloc默认类型为std::vector<_Tp>
      template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
        //>protected方式继承自_Vector_base, 继承下来的public内容会将级至protected
        //>_Vector_base为struct, 默认的访问级别为public
        class vector : protected _Vector_base<_Tp, _Alloc>
        {
          //>_Alloc_value_type即_Tp
          typedef typename _Alloc::value_type _Alloc_value_type;
          //>concept_check.h中的宏, 作类型检查, 从最后一个参数可以看出对类型作何检查
          __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
          __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
    
          //>_Base为vector基类的类型
          typedef _Vector_base<_Tp, _Alloc> _Base;
          //>_Tp_alloc_type可理解为_Alloc<_Tp>
          typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
          typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Alloc_traits;
    
        public:
          //>typedef常用的数据类型
          //>_Tp
          typedef _Tp value_type;
          //>Tp*
          typedef typename _Base::pointer pointer;
          //>const Tp*
          typedef typename _Alloc_traits::const_pointer const_pointer;
          //>_Tp&
          typedef typename _Alloc_traits::reference reference;
          //>const _Tp&
          typedef typename _Alloc_traits::const_reference const_reference;
          //>iterator
          typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
          //>const_iterator
          typedef __gnu_cxx::__normal_iterator<const_pointer, vector> const_iterator;
          //>const_reverse_iterator
          typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
          //>reverse_iterator
          typedef std::reverse_iterator<iterator> reverse_iterator;
          /**********
          namespace std
          {
            typedef __SIZE_TYPE__ size_t;
            typedef __PTRDIFF_TYPE__ ptrdiff_t;
          }
          **********/
          typedef size_t size_type;
          typedef std::ptrdiff_t difference_type;
          //>_Alloc
          typedef _Alloc allocator_type;
    
        protected:
          //>using常用于namespapce
          //>这个地方的using使用了基类的成员, 甚至可以使用基类的private成员
          //>C++11还引进了using的其它用法, 类似于typedef
          using _Base::_M_allocate;
          using _Base::_M_deallocate;
          using _Base::_M_impl;
          using _Base::_M_get_Tp_allocator;
    
        public:
          //>默认构造函数, vector为空
          vector()
          : _Base() { }
    
          //>指定_Alloc的构造函数, vector也为空
          //>explicit关键字, 构造函数可以传递一个参数时的惯用法, 防止类型隐式转换
          explicit
          vector(const allocator_type& __a)
          : _Base(__a) { }
    
    #if __cplusplus >= 201103L
          //>构造函数, 指定了vector大小和默认的内存分配器
          //>vector采取了默认的初始化方式, 调用_M_default_initialize
          explicit
          vector(size_type __n, const allocator_type& __a = allocator_type())
          : _Base(__n, __a)
          { _M_default_initialize(__n); }
    
          //>构造函数, 指定了vector大小、元素类型和默认的内存分配器
          //>通过指定的value_type初始化vector, 调用_M_fill_initialize
          vector(size_type __n, const value_type& __value,
             const allocator_type& __a = allocator_type())
          : _Base(__n, __a)
          { _M_fill_initialize(__n, __value); }
    #else
          //>构造函数, 指定了vector大小、默认的元素类型和默认的内存分配器
          //>同样, 调用_M_fill_initialize进行初始化
          explicit
          vector(size_type __n, const value_type& __value = value_type(),
             const allocator_type& __a = allocator_type())
          : _Base(__n, __a)
          { _M_fill_initialize(__n, __value); }
    #endif
    
          //>拷贝构造函数
          //>拷贝了同样的元素和内存分配器
          vector(const vector& __x)
          : _Base(__x.size(),
            _Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()))
          {
            this->_M_impl._M_finish =
              std::__uninitialized_copy_a(__x.begin(), __x.end(),
              this->_M_impl._M_start, _M_get_Tp_allocator());
          }
    
    #if __cplusplus >= 201103L
          //>rvalue版本的构造函数
          //>noexcept不抛出任何异常
          //>调用了std::move
          vector(vector&& __x) noexcept
          : _Base(std::move(__x)) { }
    
          //>指定了内存分配器的copy constructor
          //>调用了std::__uninitialized_copy_a
          vector(const vector& __x, const allocator_type& __a)
          : _Base(__x.size(), __a)
          {
            this->_M_impl._M_finish =
              std::__uninitialized_copy_a(__x.begin(), __x.end(),
              this->_M_impl._M_start, _M_get_Tp_allocator());
          }
    
          //>指定了内存分配器的move constructor
          //>当内存分配器不同时才进行真正的拷贝
          vector(vector&& __rv, const allocator_type& __m)
          : _Base(std::move(__rv), __m)
          {
            if (__rv.get_allocator() != __m)
            {
              this->_M_impl._M_finish =
                std::__uninitialized_move_a(__rv.begin(), __rv.end(),
                  this->_M_impl._M_start, _M_get_Tp_allocator());
              __rv.clear();
            }
          }
    
          //>初始化列表形式的构造函数, 会调用value_type类型的拷贝构造函数
          //>调用了_M_range_initialize
          vector(initializer_list<value_type> __l,
             const allocator_type& __a = allocator_type())
          : _Base(__a)
          {
            _M_range_initialize(__l.begin(), __l.end(),
              random_access_iterator_tag());
          }
    #endif
    
    #if __cplusplus >= 201103L
          //>函数参数为迭代器的模板构造函数, 以及默认的内存分配器
          //>调用了_M_initialize_dispatch进行初始化
          template<typename _InputIterator,
            typename = std::_RequireInputIter<_InputIterator> >
            vector(_InputIterator __first, _InputIterator __last,
              const allocator_type& __a = allocator_type())
            : _Base(__a)
            { _M_initialize_dispatch(__first, __last, __false_type()); }
    #else
          template<typename _InputIterator>
            vector(_InputIterator __first, _InputIterator __last,
              const allocator_type& __a = allocator_type())
            : _Base(__a)
            {
              typedef typename std::__is_integer<_InputIterator>::__type _Integral;
              _M_initialize_dispatch(__first, __last, _Integral());
            }
    #endif
    
          //>析构函数, 清空vector中的元素
          //>需要注意的是, 如果vector中的元素为指针的话, 指针指向的内存需要我们自己管理
          ~vector() _GLIBCXX_NOEXCEPT
          { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
                  _M_get_Tp_allocator()); }
    
          //>赋值操作符
          vector&
          operator=(const vector& __x);
    
    #if __cplusplus >= 201103L
          //>rvalue版本的赋值操作符
          //>constexpr是C++11引入的, 常量表达式
          //>调用了_M_move_assign
          vector&
          operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
          {
            constexpr bool __move_storage = 
               _Alloc_traits::_S_propagate_on_move_assign()
               || _Alloc_traits::_S_always_equal();
            _M_move_assign(std::move(__x), integral_constant<bool, __move_storage>());
            return *this;
          }
    
          //>参数为initializer_list的赋值操作符
          //>直接调用assign进行赋值
          vector&
          operator=(initializer_list<value_type> __l)
          {
            this->assign(__l.begin(), __l.end());
            return *this;
          }
    #endif
    
          //>下面是几个版本的赋值函数assign
          //>新的数据会覆盖vector中原来的数据
          //>指定了vector的长度和元素类型, 调用了_M_fill_assign
          void
          assign(size_type __n, const value_type& __val)
          { _M_fill_assign(__n, __val); }
    
    #if __cplusplus >= 201103L
          //>assign参数为迭代器的模板函数
          //>调用_M_assign_dispatch
          template<typename _InputIterator,
              typename = std::_RequireInputIter<_InputIterator>>
            void
            assign(_InputIterator __first, _InputIterator __last)
            { _M_assign_dispatch(__first, __last, __false_type()); }
    #else
          template<typename _InputIterator>
            void
            assign(_InputIterator __first, _InputIterator __last)
            {
               typedef typename std::__is_integer<_InputIterator>::__type _Integral;
               _M_assign_dispatch(__first, __last, _Integral());
            }
    #endif
    
    #if __cplusplus >= 201103L
          //>参数为initializer_list
          //>直接调用迭代器版本的assign函数, 代码简洁之道
          void
          assign(initializer_list<value_type> __l)
          { this->assign(__l.begin(), __l.end()); }
    #endif
    
          //>使用基类的分配器
          using _Base::get_allocator;
    
          //>下面是几个不同版本的begin/end函数
          //>用于获取不同版本的迭代器iterator/const_iterator
          //>begin返回的是指向vector第一个元素的迭代器
          //>end返回的是指向vector最后一个元素的下一个位置的迭代器
          iterator
          begin() _GLIBCXX_NOEXCEPT
          { return iterator(this->_M_impl._M_start); }
    
          const_iterator
          begin() const _GLIBCXX_NOEXCEPT
          { return const_iterator(this->_M_impl._M_start); }
    
          iterator
          end() _GLIBCXX_NOEXCEPT
          { return iterator(this->_M_impl._M_finish); }
    
          const_iterator
          end() const _GLIBCXX_NOEXCEPT
          { return const_iterator(this->_M_impl._M_finish); }
    
          //>下面是几个不同版本的rbegin/rend函数
          //>rbegin/rend与begin/end不同, 函数实现调用了end/begin, 返回的是返向迭代器
          //>用于获取不同版本的迭代器reverse_iterator/const_reverse_iterator
          //>rbegin返回的是指向vector最后一个元素的迭代器
          //>rend返回的是指向vector第一个元素的前一个位置的迭代器
          reverse_iterator
          rbegin() _GLIBCXX_NOEXCEPT
          { return reverse_iterator(end()); }
    
          const_reverse_iterator
          rbegin() const _GLIBCXX_NOEXCEPT
          { return const_reverse_iterator(end()); }
    
          reverse_iterator
          rend() _GLIBCXX_NOEXCEPT
          { return reverse_iterator(begin()); }
    
          const_reverse_iterator
          rend() const _GLIBCXX_NOEXCEPT
          { return const_reverse_iterator(begin()); }
    
    #if __cplusplus >= 201103L
          //>下面是几个const版本的迭代器函数
          //>cbegin/cend/crbegin/crend
          const_iterator
          cbegin() const noexcept
          { return const_iterator(this->_M_impl._M_start); }
    
          const_iterator
          cend() const noexcept
          { return const_iterator(this->_M_impl._M_finish); }
    
          const_reverse_iterator
          crbegin() const noexcept
          { return const_reverse_iterator(end()); }
    
          const_reverse_iterator
          crend() const noexcept
          { return const_reverse_iterator(begin()); }
    #endif
    
          //>获取vector实有的元素个数
          size_type
          size() const _GLIBCXX_NOEXCEPT
          { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
    
          //>获取vector可容纳元素个数的最大值
          //>但是这个最大值仅仅是个可能值, 有可能根本就达不到
          size_type
          max_size() const _GLIBCXX_NOEXCEPT
          { return _Alloc_traits::max_size(_M_get_Tp_allocator()); }
    
    #if __cplusplus >= 201103L
          //>下面是几个版本的resize, 重置vector大小
          //>vector可能被截短或者以一定的方式追加元素
          //>size变大时调用_M_default_append追加
          //>size变小时调用_M_erase_at_end移除多余的
          void
          resize(size_type __new_size)
          {
            if (__new_size > size())
              _M_default_append(__new_size - size());
            else if (__new_size < size())
              _M_erase_at_end(this->_M_impl._M_start + __new_size);
          }
    
          //>size变大时, 调用insert在vector尾端插入
          void
          resize(size_type __new_size, const value_type& __x)
          {
            if (__new_size > size())
              insert(end(), __new_size - size(), __x);
            else if (__new_size < size())
              _M_erase_at_end(this->_M_impl._M_start + __new_size);
          }
    #else
          //>带默认value_type的resize
          void
          resize(size_type __new_size, value_type __x = value_type())
          {
            if (__new_size > size())
              insert(end(), __new_size - size(), __x);
            else if (__new_size < size())
              _M_erase_at_end(this->_M_impl._M_start + __new_size);
          }
    #endif
    
    #if __cplusplus >= 201103L
          //>调整vector容量
          //>当capacity()大于size()时, 这个函数就起作用了
          //>前者大小会减小为后者大小
          //>通过_M_shrink_to_fit来实现
          void
          shrink_to_fit()
          { _M_shrink_to_fit(); }
    #endif
    
          //>获取vector的容量
          //>从函数实现可以看出capacity不小于size
          size_type
          capacity() const _GLIBCXX_NOEXCEPT
          { return size_type(this->_M_impl._M_end_of_storage
                 - this->_M_impl._M_start); }
    
          //>判断vector是否为空
          //>实现是通过迭代器判断完成的
          bool
          empty() const _GLIBCXX_NOEXCEPT
          { return begin() == end(); }
    
          //>重置vector的容量, 使其接近于size()
          //>当__n超过max_size()时会有异常std::length_error
          void
          reserve(size_type __n);
    
          //>元素访问操作符, const与非const两个版本
          //>需要注意的是, 函数实现没有检查vector索引的有效性
          //>vector索引有可能越界, 后果...断错误
          reference
          operator[](size_type __n)
          { return *(this->_M_impl._M_start + __n); }
    
          const_reference
          operator[](size_type __n) const
          { return *(this->_M_impl._M_start + __n); }
    
        protected:
          //>vector索引的有效性检查, 用于at()
          //>索引越界时会抛出std::out_of_range异常
          void
          _M_range_check(size_type __n) const
          {
            if (__n >= this->size())
              __throw_out_of_range(__N("vector::_M_range_check"));
          }
    
        public:
          //>元素访问, const与非const两个版本
          //>调用了_M_range_check()进行索引的有效性检查
          reference
          at(size_type __n)
          {
            _M_range_check(__n);
            return (*this)[__n]; 
          }
    
          const_reference
          at(size_type __n) const
          {
            _M_range_check(__n);
            return (*this)[__n];
          }
    
          //>front/back返回vector的第一个/最后一个元素
          //>函数实现对是begin()/end()返回的迭代器取引用
          //>如果vector为空的话, 函数返回的结果是不可预料的...
          reference
          front()
          { return *begin(); }
    
          const_reference
          front() const
          { return *begin(); }
    
          reference
          back()
          { return *(end() - 1); }
    
          const_reference
          back() const
          { return *(end() - 1); }
    
          //>获取vector第一个元素, 返回指针
          //>函数实现调用了front()
    #if __cplusplus >= 201103L
          _Tp*
    #else
          pointer
    #endif
          data() _GLIBCXX_NOEXCEPT
          { return std::__addressof(front()); }
    
    #if __cplusplus >= 201103L
          const _Tp*
    #else
          const_pointer
    #endif
          data() const _GLIBCXX_NOEXCEPT
          { return std::__addressof(front()); }
    
          //>追加一个元素到vector末尾
          //>从函数实现可以看出, 当size()小于capacity()时
          //>在vector末尾直接构建一个元素, 常量耗时
          //>否则会根据__cplusplus版本做不同的事
          void
          push_back(const value_type& __x)
          {
            if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
            {
              _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
              ++this->_M_impl._M_finish;
            }
            else
    #if __cplusplus >= 201103L
              _M_emplace_back_aux(__x);
    #else
              _M_insert_aux(end(), __x);
    #endif
          }
    
    #if __cplusplus >= 201103L
          //>rvalue版本
          //>通过emplace_back实现
          void
          push_back(value_type&& __x)
          { emplace_back(std::move(__x)); }
    
          //>emplace_back与push_back不同
          //>emplace_back是在vector末尾直接构建一个元素
          //>而push_back是复制、移动一个元素到vector末尾
          //>不定参数的模板函数
          template<typename... _Args>
            void
            emplace_back(_Args&&... __args);
    #endif
    
          //>从vector末尾移除一个元素
          //>操作的自然是_M_finish指针
          void
          pop_back()
          {
            --this->_M_impl._M_finish;
            _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
          }
    
    #if __cplusplus >= 201103L
          //>在__position前emplace一个元素
          //>原理同emplace_back
          template<typename... _Args>
            iterator
            emplace(iterator __position, _Args&&... __args);
    #endif
    
          //>下面是几个版本的insert
          //>在指定的位置插入元素
          iterator
          insert(iterator __position, const value_type& __x);
    
    #if __cplusplus >= 201103L
          //>通过emplace来insert rvalue版本的元素
          iterator
          insert(iterator __position, value_type&& __x)
          { return emplace(__position, std::move(__x)); }
    
          //>参数为initializer_list时直接调用迭代器版本的insert
          void
          insert(iterator __position, initializer_list<value_type> __l)
          { this->insert(__position, __l.begin(), __l.end()); }
    #endif
    
          //>调用_M_fill_insert
          void
          insert(iterator __position, size_type __n, const value_type& __x)
          { _M_fill_insert(__position, __n, __x); }
    
          //>迭代器版本的insert
          //>调用_M_insert_dispatch
    #if __cplusplus >= 201103L
          template<typename _InputIterator,
               typename = std::_RequireInputIter<_InputIterator>>
            void
            insert(iterator __position, _InputIterator __first,
               _InputIterator __last)
            { _M_insert_dispatch(__position, __first, __last, __false_type()); }
    #else
          template<typename _InputIterator>
            void
            insert(iterator __position, _InputIterator __first,
               _InputIterator __last)
            {
              typedef typename std::__is_integer<_InputIterator>::__type _Integral;
              _M_insert_dispatch(__position, __first, __last, _Integral());
            }
    #endif
    
          //>erase移除指定位置的元素
          iterator
          erase(iterator __position);
    
          //>erase移除指定范围的元素
          iterator
          erase(iterator __first, iterator __last);
    
          //>交换两个vector中的内容
          //>其实交换的就是_Vector_base::_Vector_impl中的三个指针
          void
          swap(vector& __x)
    #if __cplusplus >= 201103L
            noexcept(_Alloc_traits::_S_nothrow_swap())
    #endif
          {
            this->_M_impl._M_swap_data(__x._M_impl);
            _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
              __x._M_get_Tp_allocator());
          }
    
          //>清空vector
          //>调用_M_erase_at_end
          void
          clear() _GLIBCXX_NOEXCEPT
          { _M_erase_at_end(this->_M_impl._M_start); }
    
        protected:
          //>_M_allocate_and_copy
          //>从函数名可以看出
          //>先allocate内存, 再copy数据
          //>使用了异常处理
          //>有异常时需要释放刚才分配的内存并再次抛出异常
          //>__try/__catch/__throw_exception_again定义在exception_define.h中
          /**********
          #ifndef __EXCEPTIONS
          // If -fno-exceptions, transform error handling code to work without it.
          # define __try  if (true)
          # define __catch(X)  if (false)
          # define __throw_exception_again
          #else
          // Else proceed normally.
          # define __try  try
          # define __catch(X)  catch(X)
          # define __throw_exception_again  throw
          #endif
          **********/
          template<typename _ForwardIterator>
            pointer
            _M_allocate_and_copy(size_type __n,
              _ForwardIterator __first, _ForwardIterator __last)
            {
              pointer __result = this->_M_allocate(__n);
              __try
              {
                std::__uninitialized_copy_a(__first, __last, __result,
                  _M_get_Tp_allocator());
                return __result;
              }
              __catch(...)
              {
                _M_deallocate(__result, __n);
                __throw_exception_again;
              }
            }
    
    
          //>_M_initialize_dispatch
          //>从函数名可以看出
          //>分配了指定字节的内存后需要进行初始化
          //>初始化调用_M_fill_initialize
          template<typename _Integer>
            void
            _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
            {
              this->_M_impl._M_start = _M_allocate(static_cast<size_type>(__n));
              this->_M_impl._M_end_of_storage =
                this->_M_impl._M_start + static_cast<size_type>(__n);
              _M_fill_initialize(static_cast<size_type>(__n), __value);
            }
    
          //>_M_initialize_dispatch
          //>迭代器版本
          //>初始化调用_M_range_initialize
          template<typename _InputIterator>
            void
            _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
              __false_type)
            {
              typedef typename std::iterator_traits<_InputIterator>::
                iterator_category _IterCategory;
              _M_range_initialize(__first, __last, _IterCategory());
            }
    
          //>根据迭代器指向的内容初始化当前vector
          //>函数的第三个参数是个哑元
          //>根据哑元类型的不同, 有两个版本的_M_range_initialize
          template<typename _InputIterator>
            void
            _M_range_initialize(_InputIterator __first,
                _InputIterator __last, std::input_iterator_tag)
            {
              for (; __first != __last; ++__first)
    #if __cplusplus >= 201103L
              emplace_back(*__first);
    #else
              push_back(*__first);
    #endif
            }
    
          template<typename _ForwardIterator>
            void
            _M_range_initialize(_ForwardIterator __first,
                _ForwardIterator __last, std::forward_iterator_tag)
            {
              const size_type __n = std::distance(__first, __last);
              this->_M_impl._M_start = this->_M_allocate(__n);
              this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
              this->_M_impl._M_finish =
                std::__uninitialized_copy_a(__first, __last,
                  this->_M_impl._M_start,
                  _M_get_Tp_allocator());
            }
    
          //>_M_fill_initialize
          void
          _M_fill_initialize(size_type __n, const value_type& __value)
          {
            std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
              _M_get_Tp_allocator());
            this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
          }
    
    #if __cplusplus >= 201103L
          //>_M_default_initialize
          void
          _M_default_initialize(size_type __n)
          {
            std::__uninitialized_default_n_a(this->_M_impl._M_start, __n,
               _M_get_Tp_allocator());
            this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
          }
    #endif
    
          //>两个_M_assign_dispatch函数
          template<typename _Integer>
            void
            _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
            { _M_fill_assign(__n, __val); }
    
          template<typename _InputIterator>
            void
            _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
                __false_type)
            {
              typedef typename std::iterator_traits<_InputIterator>::
                iterator_category _IterCategory;
              _M_assign_aux(__first, __last, _IterCategory());
            }
    
          //>两个_M_assign_aux函数
          template<typename _InputIterator>
            void
            _M_assign_aux(_InputIterator __first, _InputIterator __last,
                std::input_iterator_tag);
    
          template<typename _ForwardIterator>
            void
            _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
                std::forward_iterator_tag);
    
          //>_M_fill_assign
          void
          _M_fill_assign(size_type __n, const value_type& __val);
    
          //>两个_M_insert_dispatch函数
          template<typename _Integer>
            void
            _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
                __true_type)
            { _M_fill_insert(__pos, __n, __val); }
    
          template<typename _InputIterator>
            void
            _M_insert_dispatch(iterator __pos, _InputIterator __first,
                _InputIterator __last, __false_type)
            {
              typedef typename std::iterator_traits<_InputIterator>::
                iterator_category _IterCategory;
              _M_range_insert(__pos, __first, __last, _IterCategory());
            }
    
          //>两个_M_range_insert函数
          template<typename _InputIterator>
            void
            _M_range_insert(iterator __pos, _InputIterator __first,
                _InputIterator __last, std::input_iterator_tag);
    
          template<typename _ForwardIterator>
            void
            _M_range_insert(iterator __pos, _ForwardIterator __first,
                _ForwardIterator __last, std::forward_iterator_tag);
    
          //>_M_fill_insert
          void
          _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
    
    #if __cplusplus >= 201103L
          //>用于resize(n)
          void
          _M_default_append(size_type __n);
    
          //>_M_shrink_to_fit
          bool
          _M_shrink_to_fit();
    #endif
    
    #if __cplusplus < 201103L
          //>用于insert(p, x)
          void
          _M_insert_aux(iterator __position, const value_type& __x);
    #else
          template<typename... _Args>
            void
            _M_insert_aux(iterator __position, _Args&&... __args);
    
          //>_M_emplace_back_aux
          template<typename... _Args>
            void
            _M_emplace_back_aux(_Args&&... __args);
    #endif
    
          //>vector大小检查
          size_type
          _M_check_len(size_type __n, const char* __s) const
          {
            if (max_size() - size() < __n)
              __throw_length_error(__N(__s));
    
            const size_type __len = size() + std::max(size(), __n);
            return (__len < size() || __len > max_size()) ? max_size() : __len;
          }
    
          //>用于erase(q1, q2), clear(), resize(), _M_fill_assign
          void
          _M_erase_at_end(pointer __pos)
          {
            std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());
            this->_M_impl._M_finish = __pos;
          }
    
    #if __cplusplus >= 201103L
        private:
          //>两个_M_move_assign
          void
          _M_move_assign(vector&& __x, std::true_type) noexcept
          {
            vector __tmp(get_allocator());
            this->_M_impl._M_swap_data(__tmp._M_impl);
            this->_M_impl._M_swap_data(__x._M_impl);
            if (_Alloc_traits::_S_propagate_on_move_assign())
              std::__alloc_on_move(_M_get_Tp_allocator(),
                __x._M_get_Tp_allocator());
          }
    
          void
          _M_move_assign(vector&& __x, std::false_type)
          {
            if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
              _M_move_assign(std::move(__x), std::true_type());
            else
            {
              this->assign(std::__make_move_if_noexcept_iterator(__x.begin()),
                  std::__make_move_if_noexcept_iterator(__x.end()));
              __x.clear();
            }
          }
    #endif
        };
    
    
      //>下面是几个全局的比较操作符, 全部inline
      //>两个基本的操作符是==和<
      //>其它所有的操作符都基于==和<
      template<typename _Tp, typename _Alloc>
        inline bool
        operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
        {
          return (__x.size() == __y.size()
            && std::equal(__x.begin(), __x.end(), __y.begin())); }
    
      template<typename _Tp, typename _Alloc>
        inline bool
        operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
        {
          return std::lexicographical_compare(__x.begin(), __x.end(),
             __y.begin(), __y.end()); }
    
      template<typename _Tp, typename _Alloc>
        inline bool
        operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
        { return !(__x == __y); }
    
      template<typename _Tp, typename _Alloc>
        inline bool
        operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
        { return __y < __x; }
    
      template<typename _Tp, typename _Alloc>
        inline bool
        operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
        { return !(__y < __x); }
    
      template<typename _Tp, typename _Alloc>
        inline bool
        operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
        { return !(__x < __y); }
    
      template<typename _Tp, typename _Alloc>
        inline void
        swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
        { __x.swap(__y); }
    
    _GLIBCXX_END_NAMESPACE_CONTAINER
    } // namespace std
    
    #endif /* _STL_VECTOR_H */
    展开全文
  • 后缀自动机详解

    万次阅读 多人点赞 2017-03-26 11:34:54
    后缀自动机   后缀自动机(单词的有向无环图)——是一种强有力的数据结构,让你能够解决许多字符串问题。 例如,使用后缀自动机可以在某一字符串中搜索另一字符串的所有出现位置,或者计算不同子串的个数——这...

    原论文(俄文)地址:suffix_automata

     

    后缀自动机

     

    后缀自动机(单词的有向无环图)——是一种强有力的数据结构,让你能够解决许多字符串问题。

    例如,使用后缀自动机可以在某一字符串中搜索另一字符串的所有出现位置,或者计算不同子串的个数——这都能在线性

    时间内解决。

      直觉上,后缀自动机可以被理解为所有子串的简明信息。一个重要的事实是,后缀自动机以压缩后的形式包含了一个长度

    为n的字符串的所有信息,仅需要O(n)的空间。并且,它能在O(n)时间内被构造(如果我们将字母表的大小k视作常数,否则就

    是O(n*logk))。

      历史上,Blumer等人于1983年首次提出了后缀自动机的线性规模,然后在1985-1986年,人们提出了首个线性时间内构建

    后缀自动机的算法(Crochemore,Blumer等)。在文末链接处查看更多细节。

      后缀自动机在英文中被称作“suffix automaton”(复数形式:suffix automata),单词的有向无环图——"direcged acyclic

    word graph"(简写为“DAWG”)。

     

     

    后缀自动机的定义

    定义.对给定字符串s的后缀自动机是一个最小化确定有限状态自动机,它能够接收字符串s的所有后缀。

     

     

    下面解释这一定义:

    ·        后缀自动机是一张有向无环图,其中顶点是状态,而边代表了状态之间的转移。

    ·        某一状态t_0被称作初始状态,由它能够到达其余所有状态。

    ·        自动机中的所有转移——即有向边——都被某种符号标记。从某一状态出发的诸转移必须拥有不同的标记。(另一方面,

    状态转移不能在任何字符上)。

    ·        一个或多个状态被标记为终止状态。如果我们从初始状态t_0经由任意路径走到某一终止状态,并顺序写出所有经过边的

    标记,你得到的字符串必然是s的某一后缀。

    ·        在符合上述诸条件的所有自动机中,后缀自动机有这最少的顶点数。(后缀自动机并不被要求拥有最少的边数)

    后缀自动机的最简性质

    最简性——后缀自动机的最重要性质是:它包含了所有s的子串的信息。换言之,对于任意从初始状态t_0出发的路径,如果我们

    写出所经过边上的标记,形成的子串必须是s的子串。相应地,s的任意子串都对应一条从初始状态t_0出发的路径。

    为了简化说明,我们称子串“匹配”了从初始状态出发的路径,如果该路径上的边标记组成了这一子串。相应地,我们称任意路径

    “匹配”某一子串,该子串由路径中边的标记组成。

     后缀自动机的每个状态都引领一条或多条从初始状态出发的路径。我们称这个状态有若干匹配这些路径的方法。

     

    构建后缀自动机的实例

    下面给出一些对简单的字符串构建后缀自动机的例子。

     初始状态被记作t0,终止状态用星号(*)标记。

     

    s=""

     

    s="a"

     

     

     

    s="aa"

     

    s="ab"

     

    s="aba"

     

     

     

    s="abb"

     

     

     

    s="abbb"

     

     

     

     

    一个线性时间构建后缀自动机的算法

    在我们描述构建算法之前,有必要介绍一些新的概念和简要的证明,它们对理解后缀自动机的概念十分重要。

     

    结束位置endpos,它们的性质及与后缀自动机的联系:

    考虑字符串s的任意非空子串t。我们称终点集合endpos(t)为:s中所有是t出现位置终点的集合。

    我们称两个子串t_1和t_2“终点等价”,如果它们的终点集合一致:endpos(t_1)=endpos(t_2)。因此,所有s的非空子串可

    以根据终点等价性分成若干类。

     事实上对后缀自动机,终点等价字符串仍然保持相同性质。换句话说,后缀自动机中状态数等价于所有子串的终点等价类

    个数,加上初始状态。每个状态对应一个或多个拥有相同终点集合的子串。

      我们将这一陈述作为假定,然后描述一个基于此假设的,线性时间构建后缀自动机的算法——正如我们不久后将会看到的,

    所有后缀自动机的必须性质,除最小性(即最少顶点数),都将被满足(最小性由Nerode产生,见参考文献)。

     关于终点集合,我们给出一些简单但重要的事实。

     

    引理1.两个非空子串u和v(length(u)<=length(v))是终点等价的,当且仅当u在字符串s中仅作为v的后缀出现。

     

    证明是显然的。

     

    引理2.考虑两个非空子集u,w(length(u)<=length(w))。它们的终点集合不相交,或者endpos(w)是endpos(u)的子集。进一

    步地,这取决于u是否是w的后缀:

     

     

    证明.假设两个集合endpos(u)和endpos(w)有至少一个公共元素,这就意味着字符串w和u在同一位置结束,即u是w的后缀。

    因此,在字符串w的每次出现的终点u都会出现,这就意味着endpos(w)包含于endpos(u)。

     

    引理3.考虑一个终点等价类。将该等价类中的子串按长度递减排序。排序后的序列中,每个子串将比上一个子串短,从而是

    上一个字串的后缀。换句话说,某一终点等价类中的字符串互为后缀,它们的长度依次取区间[x,y]内的所有数。

     

    证明.考虑这个终点等价类。如果它只包含一个子串,那么引理3的正确性显然。假设现在子串的个数多于一个。

     

    根据引理1,两个不同的终点等价子串总满足一个是另一个的严格后缀。因此,在同一终点等价类中的子串不可能有相同的长

    度。

     令w较长,u是等价类中的最短子串。根据引理1,u是w的严格后缀。考虑w任意一个长度为[length(u),length(w)]之间的后缀,

    由引理1,显然它在终点等价类中。

     

    后缀链接

    考虑一个状态v≠t_0.就我们目前所知,有一个确定的子串集合,其中元素和v有着相同的终点集合。并且,如果我们记w是其

    中的最长者,其余子串均是w的后缀。我们还知道w的前几个后缀(按照长度降序)在同一个终点等价类中,其余后缀(至少包括

    空后缀)在别的终点等价类中。令t是第一个这样的后缀——对它我们建立后缀链接。

      换言之,v的后缀链接link(v)指向在不同等价类中的w的最长后缀。

     在此我们假设初始状态t_0在一个单独的终点等价类中(仅包含空字符串),并且endpos(t_0)={-1,...,length(s)-1}。

     

    引理4.后缀链接组成了一棵以t_0为根的树。

     

    证明.考虑任意状态v≠t_0.后缀链接link(v)指向的状态所对应的字符串长度严格小于它本身(根据后缀链接的定义和引理3)。

    因此,沿着后缀链接移动,我们将早晚到达t_0,它对应一个空串。

     

    引理5.如果我们将所有合法的终点集合建成一棵树(使得孩子是父母的子集),这棵树将和后缀链接构成的树相同。

     

    证明.终点集合能构成一棵树这一事实由引理2得出(两个终点集合要么不相交,要么一个包含另一个)。

     

    我们现在考虑任意状态v≠t_0,及其后缀链接link(v)。根据后缀链接的定义和引理2得出:

    endpos(v)endpos(link(v))

    这和上一引理证明了我们的断言:后缀链接树和终点集合树相同。

     

    这里是一个后缀链接的例子,表示字符串"abcbc"

     

     

     

     

    小结

    在学习具体算法之前,总结上面积累的知识,并引入两个辅助符号。

     

    ·        s的所有子串可以按照它们的终点集合被分成等价类。

    ·        后缀自动机由一个初始状态t_0和所有不同的终点等价类所对应的状态组成。

    ·        每个状态v对应一个或多个字符串,我们记longest(v)是其中最长者,len(v)是其长度。我们记shortest(v)是这些字符串中

    的最短者,其长度为minlen(v)。

    ·        该状态对应的所有字符串是longest(v)的不同后缀,并且包括[minlen(v),len(v)]之间的所有长度。

    ·        对每个状态v≠t_0定义的后缀链接指向的状态对应longest(v)的长度为minlen(v)-1的后缀。后缀链接形成一棵以t_0为根的

    树,而这棵树事实上是所有终点集合的树状包含关系。minlen(v)和link(v)的关系表示如下:minlen(v)=len(link(v))+1.

    ·        如果我们从任意节点v_0开始沿后缀链接移动,我们早晚会到达初始状态t_0.在此情况下,我们得到了一系列不相交的区

    间[minlen(v_i),len(v_i)],其并集是一个连续区间。

     

    一个构建后缀自动机的线性时间算法

    我们下面描述这个算法。算法是在线的,即,逐个向s中加入字符,并适当地对当前的自动机进行修改。

     为了达到线性空间的目的,我们将只存储每个状态的len,link的值,以及转移列表。我们并不支持标记终止状态(我们将

    展示如果需要,如何在后缀自动机构建完毕后加上这些标记)。

     最初自动机由一个状态t_0组成,我们称之为0状态(其余状态将被称作1,2,...)。对此状态,令len=0,为方便起见,将link

    值设为-1(指向一个空状态)。

     因此,现在的任务就变成了实现向当前字符串末尾添加一个字符c的操作。

    下面我们描述这一操作:

     

    ·       1. 令last为对应整个字符串的状态(最初last=0,在每次字符添加操作后我们都会改变last的值)。

    ·        2.建立一个新的状态cur,令len(cur)=len(last)+1,而link(cur)的值并不确定。

    ·       3. 我们最初在last,如果它没有字符c的转移,那就添加字符c的转移,指向cur,然后走向其后缀链接,再次检查——如果没

    有字符c的转移,就添加上去。如果在某个节点已有字符c的转移,就停止,并且令p为这个状态的编号。

    ·        4.如果“某节点已有字符c的转移”这一事件从未发生,而我们来到了空状态-1(经由t_0的后缀指针前来),我们简单地令link(cur)=0,

    跳出。

    ·        5.假设我们停在了某一状态q,是从某一个状态p经字符c的转移而来。现在有两种情况:len(p)+1=len(q)或不然。

    ·        6.如果len(p)+1=len(q),那么我们简单地令link(cur)=q,跳出。

    ·        7.否则,情况就变得更加复杂。必须新建一个q的“拷贝”状态:建立一个新的状态clone,将q的数据拷贝给它(后缀链接,以及

    转移),除了len的值:需要令len(clone)=len(p)+1.

    ·        8.在拷贝之后,我们将cur的后缀链接指向clone,并将q的后缀链接重定向到clone。

    ·        9.最终,我们需要做的最后一件事情就是——从p开始沿着后缀链接走,对每个状态我们都检查是否有指向q的,字符c的转移,

    如果有就将其重定向至clone(如果没有,就终止循环)。

    ·        10.在任何情况下,无论在何处终止了这次添加操作,我们最后都将更新last的值,将其赋值为cur。

    如果我们还需要知道哪些节点是终止节点而哪些不是,我们可以在构建整个字符串的后缀自动机之后找出所有终止节点。对此我们

    考虑对应整个字符串的节点(显然,就是我们储存在变量last中的节点),我们沿着它的后缀链接走,直到到达初始状态,并且将

    途径的每个节点标记为终止节点。很好理解,如此我们标记了字符串s所有后缀的对应状态,也就是我们想要找出的终止状态。

     

    在下一节中我们从细节上考虑算法的每一步,并证明其正确性。

    这里我们仅注意一点:每个字符的添加会导致向自动机中添加一个或两个状态。因此,状态数显然是线性的。 

    转移数量的线性性,以及算法的线性时间复杂度较难理解,它们将在下面被证明,位于算法正确性的证明之后。

     

    算法的正确性证明

    ·        我们称转移(p,q)是连续的,如果len(p)+1=len(q)。否则,即len(p)+1<len(q)时,我们称之为不连续转移。

    ·        正如在算法描述中可以看到的那样,连续转移和不连续转移导致了算法流程的不同分支。连续转移)被如此命名是因为,自第

    一次出现后,它们将保持不变。相反,不连续转移可能会在向字符串中添加新字符的过程中被改变(可能会改变该边指向的状态)。

    ·        为了避免歧义,我们称s是我们已经构建了自动机的字符串,它正准备添加当前字符c。

    ·        算法开始时我们创建了新状态cur,它将匹配整个字符串s+c。我们之所以必须新建一个状态的原因是显然的——在添加新字

    符后,出现了一个新的终点等价类——一类以新字符串s+c的末尾为结尾的子串。

    ·        在创建新状态后,算法从和整个字符串s匹配的状态开始,沿着后缀链接移动,在途中试图添加指向cur的,字符c的转移。但

    我们只会在不和已存在转移冲突的情况下添加新的转移,因此一旦我们遇到了一个字符c的转移,我们就必须立刻停止。

    ·        最简单的情形——如果我们来到了空状态-1,向途中所有节点添加了字符c的转移。这就意味着字符c在字符串s中先前未曾出

    现。我们成功地添加了所有的转移,只需要记下状态cur的后缀链接——它显然必须等于0,因为这种情况下cur匹配字符串s+c的一

    切后缀。

    ·        第二种情况——当我们进入一个已存在的转移(p,q)时。这意味着我们试图向字符串中添加字符x+c(其中x是字符串s的某一后

    缀,长度为len(p)),且该字符串先前已经被加入了自动机(即,字符串x+c已经作为子串包含在字符串s中)。因为我们假设字符

    串s的自动机已被正确构建,我们并不应该添加新的转移。
    然而,cur的后缀链接指向哪里有一定复杂性。我们需要将后缀链接指向一个长度恰好和x+c相等的状态,即,该状态的len值必

    须等于len(p)+1.但这样一种情况可能并不存在:在此情况下我们必须添加一个“分割的”状态。

    ·        因此,一种可能的情形是,转移(p,q)变得连续,即,len(q)=len(p)+1.在这种情况下,事情变得简单,不必再进行任何分割,

    我们只需要将cur的后缀链接指向q。

    ·        另一种更复杂的情况——当转移不连续时,即len(q)>len(p)+1.这意味着状态q不仅仅匹配对我们必须的,长度len(p)+1的子串

    w+c,它还匹配一个更长的子串。我们不得不新建一个“分割的”状态q:将子串分割成两段,第一段将恰在长度len(p)+1处结束。

    如何实现这个“分割”呢?我们“拷贝”一个状态q,将其复制为clone,但参数len(clone)=len(p)+1.我们将q的所有转移复制给clone,

    因为无论如何我们不想改变经过p的路径。从clone出发的后缀链接总是指向q原先的后缀链接,而且q的后缀链接将指向clone。

    在拷贝之后,我们将cur的后缀链接指向clone——我们拷贝它就是为了干这个的。

     最后一步——重定向一些指向q的转移,将它们改为指向clone。哪些转移必须被重定向?只需要重定向那些匹配所有w+c的后

    缀的。即,我们需要持续沿着后缀链接移动,从p开始,只要没有到达空状态-1或者没有到达一个状态,其c的转移指向不同于q的

    状态。

     

    证明操作个数是线性的

     

    首先,我们曾经说过要保证字母表的大小是常数。否则,那么线性时间就不再成立:从一个顶点出发的转移被储存在B-树中,

    它支持按值的快速查找和添加操作。因此,如果我们记字母表的大小是k,算法的渐进复杂度将是O(n*logk),空间复杂度O(n)。但

    是,如果字母表足够小,就有可能牺牲部分空间,不采用平衡树,而对每个节点用一个长度为k的数组(支持按值的快速查找)和一

    个动态链表(支持快速遍历所有存在的键值)储存转移。这样O(n)的算法就能够运行,但需要消耗O(nk)的空间。

    因此,我们假设字母表的大小是常数,即,每个按字符查询转移的操作、添加转移、寻找下一个转移——所有这些操作我们都

    认为是O(1)的。

     如果我们观察算法的所有部分,会发现其中三处的线性时间复杂度并不显然:

     

    ·        第一处:从last状态开始,沿着后缀链接移动,并且添加字符c的转移。

    ·        第二处:将q复制给新状态clone时复制转移。

    ·        第三处:将指向q的转移重定向到clone。

    我们使用众所周知的事实:后缀自动机的大小(状态和转移的数目)是线性的。(对状态个数是线性的证明来自算法本身,对于

    移个数是线性的证明,我们将在下面给出,在实现算法之后。)。

      那么显然第一处和第二处是渐进线性的,因为每次操作都会增加新的状态和转移。

      仍然需要估算第三处总的线性复杂度——在每次添加字符时我们将指向q的转移重定向至clone。

     我们不妨关注shortest(link(last))。注意到,在沿着后缀链接上溯的过程中,当前节点的shortest的长度总是严格变小。

     显然,在向s中添加新字符之前,shortest(link(last))的长度不小于shortest(p)的长度,因为link(last)至多是p。尔后假设我们由q

    拷贝得到了节点clone,并试图从p沿后缀链接上溯,将所有通往q的转移重定向为通往clone。设v是shortest(当前节点),在clone刚

    刚建立完成后,v=short(p)。然后,在每次沿后缀链接上溯时,v的值都会变小,而如果当前节点存在经过字符c通往q的转移,就意

    味着q对应的字符串集合中包含v+c,也意味着clone包含的字符串集合中包含v+c。换言之,我们为clone包含的字符串集合找到了一

    个更短的元素,即减少了short(clone)的长度。

    在“向s中添加新字符”的整个流程结束后,有link(last)=link(cur)=clone。根据上面的讨论,新的shortest(link(last))的长度变小(或

    保持不变),而且这一长度减小的值和上溯的操作数同阶。

     综上,shortest(link(last))作为s一个后缀的起始位置在整个过程中不断右移,而且每次沿后缀指针上溯都会导致该位置严格右移。

    由于在程序结束时这一起始位置不超过n,所以这一过程的时间复杂度是线性的。

     (虽然没什么用,但同样的讨论可以被用来证明第一处的线性性,以代替对状态个数线性性的证明。)

     

    算法的实现

    首先我们描述一个数据结构,它储存特定的一段信息(len,link,转移列表)。如有必要,你可以增加表示终止状态的标签,以及其他需要

    的信息。

    我们用STL容器map存储转移列表,其空间复杂度为O(n),而处理整个字符串的时间复杂度为O(n*logk)。

     

    struct state {
    	int len,link;
    	map<char,int> next;
    };
    

     

     

    后缀自动机本身将被储存在一个state类型的数组中。正如下一节中将证明的那样,如果程序中所处理字符串的最大可能长度是MAXN,

    那么至多会占用2*MAXN-1个状态。同时,我们储存变量last——当前匹配整个字符串的状态。

     

    const int MAXLEN = 100000;
    state st[MAXLEN*2];
    int sz, last;
    

     

    我们给出初始化后缀自动机的函数(新建一个初始状态):

     

    void sa_init() {
       sz = last = 0;
       st[0].len = 0;
       st[0].link = -1;
       ++sz;
    	/*
    	// 若关于不同的字符串多次建立后缀自动机,就需要执行这些代码:
    	for (int i=0; i<MAXLEN*2; ++i)
    		st[i].next.clear();
    	*/
    }
    

     

     

     

     

     

    最后,我们给出基础函数的实现——向当前字符串的尾部添加一个字符,并相应地修改后缀自动机:

     

    void sa_extend (char c) {
    	int cur = sz++;
    	st[cur].len = st[last].len + 1;
    	int p;
    	for (p=last; p!=-1 && !st[p].next.count(c); p=st[p].link)
    		st[p].next[c] = cur;
    	if (p == -1)
    		st[cur].link = 0;
    	else {
    		int q = st[p].next[c];
    		if (st[p].len + 1 == st[q].len)
    		st[cur].link = q;
    		else {
    		int clone = sz++;
    			st[clone].len = st[p].len + 1;
    			st[clone].next = st[q].next;
    			st[clone].link = st[q].link;
    			for (; p!=-1 && st[p].next[c]==q; p=st[p].link)
    			st[p].next[c] = clone;
    			st[q].link = st[cur].link = clone;
    		}
    	}
    	last = cur;
    }
    

     

     

     

     

     

    像前面提到的那样,如果牺牲部分空间(空间复杂度增至O(nk),其中k是字母表大小),就能够对任何k实现O(n)构建自动机——但这将

    会在每个状态中建立一个长度为k的数组(用于快速按字符查询转移)和一个转移链表(用于快速遍历或者复制所有转移)。

     

    后缀自动机的其他性质

     

    状态的数量

    由长度为n的字符串s建立的后缀自动机的状态个数不超过2n-1(对于n>=3)。

    上面描述的算法证明了这一性质(最初自动机包含一个初始节点,第一步和第二步都会添加一个状态,余下的n-2步每步至多由于需要分割,增加两个状态)。

    不过,即使不涉及算法,这一性质也容易证明。注意到状态个数等于不同的终点集合的个数。此外,终点集合按“子女是父节点的不同子集”这一原则构成一棵树。

    考虑这棵树,将其稍作扩充:若一个内部节点只有一个儿子,那就意味着该儿子的终点集合不包含其父亲终点集合中的至少一个值;那么我们就创建一个虚拟节点,

    其终点集合为这个值。最终,我们得到了一棵树,其内部节点度数均>1,而叶子节点个数不超过n。因此,这棵树的结点个数不超过2n-1.自然,原树的结点个数也

    不超过2n-1.

    这样我们就独立于算法地证明了这一性质。

    有趣的是,这一上限无法被改善,即存在达到这一上限的例子: 

    "abbbb..."

    从第三次开始,每次添加字符时都会进行分割,因此结点个数将达到2n-1.

     

    转移的数量

    由长度为n的字符串s建立的后缀自动机中,转移的数量不超过3n-4(对于n>=3)。

     

    证明.

     我们计算“连续的”转移个数。考虑以t_0为初始节点的自动机的最长路径树。这棵树将包含所有连续的转移,树的边数比结点个数小1,这意

    味着连续的转移个数不超过2n-2.

      我们再来计算不连续的转移个数。考虑每个不连续转移;假设该转移——转移(p,q),标记为c。对自动机运行一个合适的字符串u+c+w,其

    中字符串u表示从初始状态到p经过的最长路径,w表示从q到任意终止节点经过的最长路径。一方面,对所有不连续转移,字符串u+c+w都是不同

    的(因为字符串u和w仅包含连续转移)。另一方面,每个这样的字符串u+c+w,由于在终止状态结束,它必然是完整串s的一个后缀。由于s的非

    空后缀仅有n个,并且完整串s不能是某个u+c+w(因为完整串s匹配一条包含n个连续转移的路径),那么不连续转移的总共个数不超过n-1.

      将这两个限制加起来,我们就得到了总数限制3n-3.注意到虽然状态个数限制可以被数据"abbbb..."达到,但这个数据并未达到3n-3的转移个数

    上限。它的转移个数是3n-4,符合要求。

      有趣的是,仍然存在达到转移个数上限的数据:

    "abbb...bbbc"

    与后缀树的联系,在后缀自动机上建立后缀树及反之

      我们证明两个定理,它们能说明后缀树和后缀自动机之间的相互关系。

    首先我们假定输入字符串的每个后缀都在其后缀树中对应一个节点(对于任意字符串而言并不一定成立:例如,对于字符串 "aaa...")。在后缀

    树的典型实现中,我们通过在字符串的末尾加上一个特殊符号(例如"#"或"$")来保证这一点。

      方便起见,我们引入如下记号:rev(s)——将字符串s反过来写,DAWG(s)——这是由字符串s建立的后缀自动机,ST(s)——这是s的后缀树。

      我们介绍“扩展指针”的概念:对于树节点v和字符c,ext[c,v]指向树中对应于字符串c+v的节点(如果路径c+v在某边的终点结束,那就将其指向该

    边的较低点);如果这样一条路径c+v不在树中,那么扩展指针未定义。在某种意义上,扩展指针的对立面就是后缀链接。

     

    定理1.DAWG(s)中后缀链接组成的树就是后缀树ST(rev(s))

     

    定理2.图DAWG(s)的边都能用后缀树ST(rev(s))的扩展指针表示。另外,DAWG(s)中的连续转移就是ST(rev(s))中反向的后缀指针。

     

    这两条定理允许使用两个数据结构之一在O(n)的时间内构建另外一个——这两个简单的算法将在下面定理3,4讨论。

      出于说明需要,我们下面展示一个包含后缀链接的后缀自动机的例子,以及其倒序字符串的相应后缀树。例如,令字符

    串s="abcbc"。

      DAWG("abcbc")(出于简便我们在每个状态上标出其识别的最长串):


     

     

    ST("cbcba")

     

     

     

    引理.

    对任意两个子串u和w,如下三个陈述是等价的:

    ·        在字符串s中endpos(u)=endpos(w)

    ·        在字符串rev(s)中firstpos(rev(u))=firstpos(rev(w))

    ·        在后缀树ST(rev(s))中,rev(u)和rev(w)匹配从根开始的一段相同路径。

     

    证明十分显然:如果两个字符串的起始位置集合相同,那么一个字符串只作为另外一个的前缀出现,这意味着在后缀树中,二者之

    间并没有其他节点。

     因此,后缀自动机中的状态和后缀树中的节点一一对应。

     

    定理1的证明.

     后缀自动机中的状态和后缀树中的节点一一对应.

     

    考虑任意后缀链接y=link(x)。根据后缀链接的定义,longest(y)是longest(x)的一个后缀,并且y是所有满足条件(和x的终点集合不同)

    的状态中使len(y)最大者。

     在rev(s)中,这意味着link(x)指向x所对应字符串的最长前缀,该前缀对应一个不同的状态y。换句话说,后缀链接link(x)指向后缀树中节

    点x的父亲。

     

    定理2的证明.

     

    后缀自动机中的状态和后缀树中的节点一一对应。

     

    考虑后缀自动机DAWG(s)中的任意转移(x,y,c)。这意味着y是包含子串longest(x)+c的终点集合等价类。对于rev(s),y对应了一个子串,

    该子串的firstpos(在文本rev(s)中)和c+rev(longest(x))的firstpos相同。

     这意味着:

    rev(longest(y))=ext[c,rev(longest(x))].

    (注:这里的用法并不严谨……请自行把字符串和节点对应) 

    也就是该定理的第一部分,我们还需要证明第二部分:自动机中的所有连续转移对应树中的后缀指针。对于连续转移,有length(y)=length(x)+1,

    即在标识字符c后我们到达了一个状态,它是一个不同的等价类。这意味着在rev(s)的后缀树中,x节点对应的字符串恰好是y节点所对应字符串的,长

    度比它小1的后缀——也就是说,后缀树中y的后缀指针指向x,(x,y)就是树中的反向后缀指针。

     

    定理得证。

     

    定理3.

    使用后缀自动机DAWG(s),我们可以用O(n)的时间构建后缀树ST(rev(s))。

     

    定理4.

    使用后缀树ST(rev(s)),我们可以用O(n)的时间构建后缀自动机DAWG(s)。

     

    定理3的证明.

    后缀树ST(rev(s))的节点和DAWG(s)中的状态一一对应。树中与自动机中状态v相对应的节点表示一个长度为len(v)的字符串。

     

    根据定理1,ST(rev(s))中的边恰好是把DAWG(s)的后缀链接反向,而边的标记可以借助不同状态的len计算(译者注:从叶子开始,利用自动

    机中状态的len值计算后缀树中的节点对应于哪个子串),或者更方便地,对自动机中每个状态我们都能知道其endpos集合中的一个元素(在构建

    后缀自动机时维护)。

     至于树中的后缀指针,我们可以基于定理2构建:查找自动机中所有的连续转移,对所有这样的转移(x,y)我们都在树中添加一个后缀指针link[y]=x。

     因此,在O(n)时间内我们就可以构建一棵后缀树及其中的后缀指针。

     (如果我们认为字母表的大小k并非常数,那么重建操作将花费O(n*logk)的时间。)

     

    定理4的证明.

    后缀自动机DAWG(s)包含的状态和ST(rev(s))中的节点一一对应。对每个状态v,其对应的最长字符串longest(v)都和后缀树中从根到v的路径翻转后

    形成的字符串相同。

     

    根据定理2,为了构建自动机中的所有转移,我们需要找到所有扩展ext[c,v]的指针。

     首先,注意到其中的一些指针直接由树中的后缀指针得到。事实上,如果对于树中任意节点x,我们考虑其后缀指针y=link[x],那就意味着自动机中

    有一个从y指向x的连续转移,标记为树节点x所对应字符串的第一个字符。

     不过,只是这样我们并不能找到所有的扩展。额外地,有必要从叶子到根遍历后缀树,而且对于每个节点v都遍历其所有儿子,对每个儿子观察所有

    扩展指针ext[c,w],如果该指针上的字符c在节点v中还未发现,就将其复制到v中:

    ext[c,v]=ext[c,w],如果ext[c,w]=nil.

    这一过程将在O(n)时间内完成,如果我们认为字母表的大小是常数。

    最终,还需要建立后缀自动机中的后缀链接。而根据定理1,后缀链接可以直接由后缀树ST(rev(s))的边获得。

    这样,我们就得到使用从倒序字符串的后缀树建立后缀指针的O(n)算法。

     (不过,若字母表的大小k是变量,那么渐进复杂度就是O(n*logk))。

     

    在解决问题中的应用

    下面看在后缀自动机的帮助下我们能做什么。

     

    简便起见,我们假设字母表的大小k为常数。

     

    存在性查询

     

    问题.给定文本T,询问格式如下:给定字符串P,问P是否是T的子串。 

    复杂度要求.预处理O(length(T)),每次询问O(P)。

     

    算法.我们对文本T用O(length(T))建立后缀自动机。

    现在回答单次询问。假设状态——变量v,最初是初始状态T_0.我们沿字符串P给出的路径走,因此从当前状态经转移来到新的状态v

    。如果在某时刻,当前状态没有要求字符的转移,那么答案就是"no"。如果我们处理了整个字符串P,答案就是"yes"。

    显然这一算法将在时间O(length(P))内运行完毕。并且,该算法实际上找出了P在文本中出现过的最长前缀——如果模式串使得这些前缀

    都很短,算法将比处理全部模式串要快得多。

     

    不同的子串个数

     

    问题.给定字符串S,问它有多少不同的子串。

     复杂度要求.O(length(S))。

     

    算法.我们将字符串S建立后缀自动机。

     在后缀自动机中,S的任意子串都对应自动机中的一条路径。答案就是从初始节点t_0开始,自动机中不同的路径条数。

     已知后缀自动机是一张有向无环图,我们可以考虑用动态规划计算不同的路径数量。

      也就是,令d[v]为从状态v开始的不同路径条数(包括长度为零的路径),则有转移:


     

     

     

     

     

    即d[v]是v所有后继节点的d值之和加上1.

    最终答案就是d[t_0]-1(减一以忽略空串)。

     

    不同子串的总长

     

    问题.给定字符串S,求其所有不同子串的总长度。

    复杂度要求.O(length(S)).

     

    算法.这一问题的答案和上一题类似,但现在我们必须考虑两个状态:不同子串的个数d[v]和它们的总长ans[v].

      上一题已描述了d[v]的计算方法,而ans[v]的计算方法如下:

     

    即取所有后继节点w的ans值,并将它和d[w]相加。因为这是每个字符串的首字母。

     

    字典序第k小子串

     

    问题.给定字符串S,一系列询问——给出整数K_i,计算S的所有子串排序后的第K_i个。

    复杂度要求.单次询问O(length(ans)*Alphabet),其中ans是该询问的答案,Alphabet是字母表大小。

     

     算法.这一问题的基础思路和上两题类似。字典序第k小子串——自动机中字典序第k小的路径。因此,考虑从每个状态出

    发的不同路径数,我们将得以轻松地确定第k小路径,从初始状态开始逐位确定答案。

     

    最小循环移位

     

    问题.给定字符串S,找到和它循环同构的字典序最小字符串。

     复杂度要求.O(length(S)).

     

    算法.我们将字符串S+S建立后缀自动机。该自动机将包含和S循环同构的所有字符串。

     从而,问题就简化成了在自动机中找出字典序最小的,长度为length(S)的路径,这很简单:从初始状态开始,每一步都贪心地走

    ,经过最小的转移。

     

    出现次数查询

     

    问题.给定文本T,询问格式如下:给定字符串P,希望找出P作为子串在文本T中出现了多少次(出现区间可以相交)。

     复杂度要求.预处理O(length(T)),单次询问O(length(P)).

     

    算法.我们将文本T建立后缀自动机。

     然后我们需要进行预处理:对自动机中的每个状态v都计算cnt[v],等于其endpos(v)集合的大小。事实上,所有在T中对应同一状态的

    字符串都在T中出现了相同次数,该次数等于endpos中的位置数。

     不过,我们无法对所有状态明确记录endpos集合,所以我们只计算其大小cnt.

     为了实现这一点,如下处理。对每个状态,如果它不是由“拷贝”而来,最初就赋值cnt=1.然后我们按长度len降序遍历所有序列,并将

    当前的cnt[v]加给后缀链接:

     cnt[link(v)]+=cnt[v].

      你可能会说我们并没有对每个状态计算出了正确的cnt值。

     为什么这是对的?不经“拷贝”而来的状态恰好有length(S)个,而且其中的第i个是我们添加第i个字符时得到的。因此,最初这些状态的cnt=1,

    其他状态的cnt=0.

     然后我们对每个状态v执行如下操作:cnt[link(v)]+=cnt[v].其意义在于,如果某字符串对应状态v,曾在cnt[v]中出现过,那么它的所有后缀都

    同样在其中出现。

     这样,我们就掌握了如何对自动机中所有状态计算cnt值的方法。

     在此之后,询问的答案就变得平凡——只需要返回cnt[t],其中t是模式串P所对应的状态。

     

    首次出现位置查询

     

    问题.给定文本T,询问格式如下:给定字符串P,求P在文本中第一次出现的位置。

     复杂度要求.预处理O(length(T)),单次询问O(length(P)).

     

    算法.对文本T建立后缀自动机。

     为了解决这一问题,我们需要预处理firstpos,找到自动机中所有状态的出现位置,即,对每个状态v我们希望找到一个位置firstpos[v],代表

    其第一次出现的位置。换句话说,我们希望预先找出每个endpos(v)中的最小元素(我们无法明确记录整个endpos集合)。

      维护这些firstpos的最简单方法是在构建自动机时一并计算,当我们创建新的状态cur时,一旦进入函数sa_extend(),就确定该值:

     firstpos(cur)=len(cur)-1(如果我们的下标从0开始)。

    当拷贝节点q时,令:

     firstpos(clone)=firstpos(q),(因为只有一个别的可能值——firstpos(cur),显然更大)。

     这样就得到了查询的答案——firstpos(t)-length(P)+1,其中t是模式串P对应的状态。

     

    所有出现位置查询

     

    问题.给定文本T,询问格式如下:给定字符串P,要求给出P在T中的所有出现位置(出现区间可以相交)。

    复杂度要求.预处理O(length(T))。单次询问O(length(P)+answer(P)),其中answer(P)是答案集合的大小,即,要求时间复杂度和输入输出同阶。

     

    算法.对文本T建立后缀自动机,和上一个问题相似,在构建自动机的过程中对每个状态计算第一次出现的终点firstpos。

     

    假设我们收到了一个询问——字符串P。我们找到了它对应的状态t。

     显然应当返回firstpos(t)。还有哪些位置?我们考虑自动机中那些包含了字符串P的状态,即那些P是其后缀的状态。

     换言之,我们需要找出所有能通过后缀链接到达状态t的状态。

     因此,为了解决这一问题,我们需要对每个节点储存指向它的所有后缀链接。为了找到答案,我们需要沿着这些翻转的后缀链接进行DFS/BFS,从状

    态t开始。

     这一遍历将在O(answer(P))时间内结束,因为我们不会访问同一状态两次(因为每个状态的后缀链接仅指向一个点,因此不可能有两条路径通往同一

    状态)。

     然而,两个状态的firstpos值可能会相同,如果一个状态是由另一个拷贝而来。但这不会影响渐进复杂度,因为每个非拷贝得到的节点只会有一个拷贝。

     此外,你可以轻松地除去那些重复的位置,如果我们不考虑那些拷贝得来的状态的firstpos。事实上,所有拷贝得来的状态都被其“母本”状态的后缀链接

    指向。因此,我们对每个节点记录标签is_clon,我们不考虑那些is_clon=true的状态的firstpos。这样我们就得到了answer(P)个不重复地状态。

     给出一个离线版本的实现:

     

    struct state {
    	...
    	bool is_clon;
    	int first_pos;
    	vector<int> inv_link;
    	};
    	
    	 
    ... 后缀自动机构建完毕 ...
    for (int v=1; v<sz; ++v)
    	st[st[v].link].inv_link.push_back (v);
    ...
      
     
    // 回答询问--返回所有的出现位置(出现区间可能有重叠)
    void output_all_occurences (int v, int P_length) {
       if (! st[v].is_clon)
    		cout << st[v].first_pos - P_length + 1 << endl;
       for (size_t i=0; i<st[v].inv_link.size(); ++i)
    		output_all_occurences (st[v].inv_link[i], P_length);
    }
    

     

     

     

    查询不在文本中出现的最短字符串

    问题.给定字符串S和字母表。要求找出一个长度最短的字符串,使得它不是S的子串。

    复杂度要求.O(length(S)).

     

     算法.在字符串S的后缀自动机上进行动态规划。

     令d[v]为节点v的答案,即,我们已经输入了字符串的一部分,匹配到v,我们希望找出有待添加的最少字符数量,以到达一个不存在的转移。

     计算d[v]非常简单。如果在v处某个转移不存在,那么d[v]=1:用这个字符来“跳出”自动机,以得到所求字符串。

     否则,一个字符串无法达到要求,因此我们必须取所有字符中的最小答案:

     

    原问题的答案等于d[t_0],而所求字符串可以用记录转移路径的方法得到。

     

    求两个字符串的最长公共子串

     

    问题.给定两个字符串S和T。要求找出它们的最长公共子串,即一个字符串X,它同时是S和T的子串。

      复杂度要求.O(length(S)+length(T)).

     

    算法.我们对字符串S建立后缀自动机。

     

    我们按照字符串T在自动机上走,查找它每个前缀在S中出现过的最长后缀。换句话说,对字符串T中的每个位置,我们都想找出S和T在该位置结束的最长公共子串。

     

    为了实现这一点,我们定义两个变量:当前状态v和当前长度l。这两个变量描述了当前的匹配部分:其长度和状态,对应哪个字符串(如果不储存长度就无法确定这一点,因为一个状态可能匹配多个有不同长度的字符串)。

     

    最初,p=t_0,l=0,即,匹配部分为空。

     

    现在我们考虑字符T[i],我们希望找到这个位置的答案。

    ·        如果自动机中的状态v有一个符号T[i]的转移,我们可以简单地走这个转移,然后将长度l加一。

    ·        如果状态v没有该转移,我们应当尝试缩短当前匹配部分,为此应当沿着后缀链接走:
    v=link(v).
    在此情况下,当前匹配长度必须被减少,但留下的部分尽可能多。显然,应令l=len(v):
    l=len(v).
    若新到达的状态仍然没有我们想要的转移,那我们必须再次沿着后缀链接走,并且减少l的值,直到我们找到一个转移(那就返回第一步),或者我们最终到达了空状态-1(这意味着字符T[i]并未在S中出现,所以令v=l=0然后继续处理下一个i)。

    原问题的答案就是l曾经达到的最大值。

     

    这种遍历方法的渐进复杂度是O(length(T)),因为在一次移动中我们要么将l加一,要么沿着后缀链接走了若干次,每次都会严格减少l。因此,l总共的减少值之和不可能超过length(T),这意味着线性时间复杂度。

     

    代码实现:

     

    string lcs (string s, string t) {
    	sa_init();
    	for (int i=0; i<(int)s.length(); ++i)
    		sa_extend (s[i]);
    	
    	int v = 0,  l = 0,
    		best = 0,  bestpos = 0;
    	for (int i=0; i<(int)t.length(); ++i) {
    		while (v && ! st[v].next.count(t[i])) {
    			v = st[v].link;
    			l = st[v].length;
    		}
    		if (st[v].next.count(t[i])) {
    		v = st[v].next[t[i]];
    		 ++l;
    		}
    		if (l > best)
    			best = l,  bestpos = i;
    	}
    	return t.substr (bestpos-best+1, best);
    }
    

     

     

    多个字符串的最长公共子串

     

    问题.给出K个字符串S_1~S_K。要求找出它们的最长公共子串,即一个字符串X,它是所有S_i的子串。

      复杂度要求.O(∑length(S_I)*K).

     

    算法.将所有S_i连接在一起成为一个新的字符串T,其中每个S_i后要加上一个不同的分隔符D_i(即加上K个额外的不同特殊字符D_1~D_K):

     

    我们对字符串T构建后缀自动机。

     现在我们需要在后缀自动机找出一个字符串,它是所有字符串S_i的子串。注意到如果一个子串在某个字符串S_j中出现过,那么后缀自动机中存在一

    条以这个子串为前缀的路径,包含分隔符D_j,但不包含其他分隔符D_1,...,D_j-1,D_j+1,...,D_k。

     因此,我们需要计算“可达性”:对自动机中的每个状态和每个字符D_i,计算是否有一条从该状态开始的路径,包含分隔符D_i,但不包含别的分隔符。

    很容易用DFS/BFS或者动态规划实现。在此之后,原问题的答案就是字符串longest(v),其中v能够到达所有的分隔符。

     

    OJ上的题目

    可以用后缀自动机解决的题目:

    SPOJ#7258 SUBLEX"Lexicographical Substring Search"

    BZOJ#2555 Substring

    SPOJ#8222 NSUBSTR"Substrings"

    SPOJ#1812 LCS2"Longest Common Substrings II"

    BZOJ#3998 弦论

     

    参考文献

    我们首先给出和后缀自动机有关的一些第一手研究:

    ·        A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, R.McConnell.Linear Size Finite Automata for the Set of All Subwordsof a Word. An Outline of Results [1983]

    ·        A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler.The SmallestAutomaton Recognizing the Subwords of a Text[1984]

    ·        Maxime Crochemore. OptimalFactor Transducers [1985]

    ·        Maxime Crochemore. Transducersand Repetitions [1986]

    ·        A. Nerode. Linear automatontransformations [1958]

    此外,还有一些当代资源,这一主题在许多有关字符串算法的书籍中被提到:

    ·        Maxime Crochemore, Wowjcieh Rytter. Jewels ofStringology [2002]

    ·        Bill Smyth. Computing Patterns in Strings [2003]

    ·        Билл Смит. Методы и алгоритмы вычислений на строках [2006]

     

     

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • bit_vector位向量容器

    2020-02-01 18:16:35
    bit_vector位向量容器 一、原理 bit_vector位向量容器是一个bit位元素的序列容器,具有vector容器一样的成员函数,常用于硬件端口的控制...bit_vectorvector后缀名,实际与vector并没有任何关联。 bit_vecto...

    bit_vector位向量容器

    一、原理

    bit_vector位向量容器是一个bit位元素的序列容器,具有vector容器一样的成员函数,常用于硬件端口的控制。区别于vector<bool>的一个重要特性是bit_vector更节省内存空间,一个元素只占用一个bit,而不是一个字节。bit_vector用vector作后缀名,实际与vector并没有任何关联。

    bit_vector容器的每个元素是一个 bit 位值,取 0 或 1,连续分配在以字为单位的字节块中。

        bit_vector容器的实现,首先需要解决若干bit位的内存分配和迭代器对bit位元素的随机读写问题。 

        bit 位的内存分配,由内存分配器根据 bit 位的个数需求,一次性地分配若干字,以后通过动态分配内存进行bit位的添加。 

    随机访问迭代器,通过所在的字和位的偏移给出一个 bit 位的确切位置。bit 位的随机读写,利用C++的bit位操作运算,如位与、位或和异或等,判断某个bit位值为1或0,或设置某个bit位为1或0。

    如图所示,假设为bit位分配了连续的3个机器字的空间,共6个字节,16×3=48个 bit。为了对灰色的 bit 位进行读写,Bit_reference 结构体使用了一个标志 bit 位所在字的M_p指针变量,它的类型为unsigned int*,正好作为一个字的指针类型。此外,还使用一个M_mask变量,标记bit位在这个字中的偏移量。对于图所示的情形,M_p指向灰色bit位所在的第2个字,M_mask为0010000000000000,唯一的一个“1”,表示当前读写的bit位的位置。

        实现代码可参见SGI的stl_bvector.h文件。

    二、应用

    类同vector,只是由以前的一个数据类型(如int等)变成bool型对象。如:下面的 insert 函数,在pos位置前插入一个新的bit位元素,元素值由x给出。 

    iterator insert(iterator pos, bool x)//x为0或1

    利用bit_vector位向量容器,可直观地对整型数据的bit位进行处理。一串bit位数据可直接逐位写入容器,而不需要先将若干bit位转换为整数才可写入某个整型变量。 

    从实现源码来看,bit_vector容器与vector基本上具有相同的接口,只是bit_vector的迭代器稍为复杂些,需要通过bit位所在的字和字中的偏移量给出当前bit位的位置。总的来说,bit_vector容器的功能,vector<bool>也可以实现,只是使用vector要用一个字节表示一个bit。明显地,从算法的空间复杂度考虑,vector<boo>不及bit_vector划算。

    展开全文
  • typedef vector < string > FilesList ; void ls ( const string & sDir , FilesList & files , const char * acExtension ) ; int...
  • C++后缀表达式

    千次阅读 2018-06-08 18:12:05
    1 基本概念后缀表示法也叫逆波兰表示法(前缀就是波兰表示法),由于所有的操作符都在操作数的后面,所以被称为后缀表示法。中缀表示法的操作符在操作数之间,也是最符合人的逻辑。前缀表示法的操作符在操作数之前,...
  • 栈的使用场景之一,中缀表达式转为后缀表达式。  将中缀表达式拆分成各个数字和运算符,并去除了括号,存到数组(或者容器、队列)中,遍历之: 若是数字,直接存放到用于输出的数组(或者容器、队列)中 若是”(...
  • 【Unity】Mathd系列(一)Double型Vector2

    千次阅读 2018-03-31 18:50:44
    由于Unity中的向量用的都是float型去存储,而float型的精度只有五位小数,导致了前段时间做项目的时候出现了精度上的问题。...首先是Vector2d:/// Vector2d.cs /// /// The double type version of the Unit...
  • 摘要: 本文介绍了C++标准库中的容器类vector,分析了它的优点,并且建议在应用程序中使用它作为动态数组的优先选择,而不是MFC的CArray<>等其他类模板。最后介绍了vector的接口和使用时的注意事项。 在一些...
  • 使用堆栈计算后缀表达式

    千次阅读 2019-01-29 16:01:18
    使用堆栈计算后缀表达式 一、实现栈结构 根据栈的先进后出的特点,很容易设置栈结构的接口:入栈、出栈、判空、size()等。可以用线性表的方法来实现一个栈结构,其实也就两种,用链表或数组实现栈。 但是,在C++...
  • suffix array后缀数组一般用于字符串匹配问题当中,一般来说可以用suffix tree解决的字符串匹配问题用suffix array都可以解决. 主要参考了geeksforgeeks上关于后缀数组和lcp(longest common prefix)的教程. ...
  • 利用后缀数组构造后缀

    千次阅读 2016-04-24 19:06:49
    如果确实需要,可以改成vector存图,或者手动翻转链表中的元素,不会影响时间复杂度。 不考虑后缀数组部分,建后缀树的函数是O(n)的。虽然有两层循环,但是显然后缀树中一条边只会在新建的时候被访问一次,且...
  • 后缀树与后缀数组

    千次阅读 2013-10-30 21:08:36
    后缀树和后缀数组简直就是 ACM 选手必备的知识啊,我已经在两次比赛中碰到过相关的问题了。我甚至还写过一篇应用的文章,可是我真是井底之蛙啊,那时我还不知道这个叫后缀数组,还有更好的构造算法,还有很多的应用...
  • 类似的就是vectorvector 是同一种类型的对象的集合,每个对象都有一个对应的整数索引值。和 string 对象一样,标准库将负责管理与存储元素相关的内存。我们把 vector 称为容器,是因为它可以包含其他对象...
  • java_集合体系之Vector详解、源码及示例——05

    千次阅读 多人点赞 2013-12-23 14:40:54
    摘要: 本文通过对Vector的结构图中涉及到的类、接口来说明Vector的特性、通过源码来深入了解Vector各种功能的实现原理、通过示例加深对Vector的理解。
  • 后缀子串排序

    2017-07-29 21:20:42
    后缀子串排序 xcyk–>wwm data:2017/07/29 21:18题目描述:对于一个字符串,将其后缀子串进行排序,例如grain其子串有:grain rain ain in n然后对各子串按字典顺序排序,即: ain,grain,in,n,rain 输入:每个案例...
  • 计算后缀表达式

    千次阅读 2018-08-15 20:02:24
    一、通过栈把中缀表达式转换为后缀表达式的步骤: 从左至右扫描中缀表达式, if(遇到数字){  加入后缀表达式 }else if(遇到 ‘(’ ){  入栈 }else if(遇到 ‘)’ ){  依次将栈中元素出栈并加入到后缀...
  • 后缀排序 后缀自动机的应用

    千次阅读 2016-08-31 13:57:34
    同步个人博客 http://sxysxy.org/blogs/23 到csdn)给一字符串的所有后缀排个序输出,字符串长度 排序要求字典序小的在前面,在满足这个条件的情况下,短的后缀放到前面例如ababa的后缀排序结果是[a, aba, ababa, ba,...
  • 最近上课需要做简单计算器,涉及到数据结构栈的应用,实现了字符串计算式中缀转后缀,并进行计算,写的可能有点乱,完全按自己思路写的。 #include<iostream> using namespace std; #include<vector> #...
  • 堆栈实现中缀表达式转为后缀表达式 (1)规则  中缀表达式转为后缀表达式也有一定的规则,这个规则是根据操作符的运算优先级来定的转为后缀表达式的规则为: 如果遇到操作数,我们就直接将其输出。 如果遇到...
  • vi插入五个整数,删除里面的奇数,然后输出结果 vs插入五个字符串,删除字符串中后缀为奇数的字符串,然后输出结果
  • anki_vector SDK源码解析(教程)

    千次阅读 2018-12-25 10:13:00
    一:最近anki vector robot开放了Python SDK,我听到的第一时间就赶快上网查了查,先抛几个官网重要链接吧: Python编程API手册及环境搭建等:  ...
  • #include <iostream>...vector> #include <stack> using namespace std; int computePostfixExpression(vector<char> postfixExpression) { stack<int> operands; ...
  • 分两种情况:中缀表达式和后缀表达式。 中缀表达式求值:先将中缀表达式建立二叉树转后缀表达式,然后再求值。 尝试1: #include &lt;iostream&gt; #include &lt;string&gt; #include &lt;...
  • 后缀表达式 详解

    2014-09-05 13:37:05
    表达式的表示形式有中缀、前缀和后缀3中形式。中缀表达式按操作符的优先级进行计算(后面代码实现只包括+、-、*、\,小括号),即数学运算。 后缀表达式中只有操作数和操作符。操作符在两个操作数之后。它的计算规则...
  • 要访问字体对象,只需将Font后缀添加到字体名称中。 // Include the font file in your project like any other module. include ( 'fonts/camBamStick1.js' ) ; function main ( params ) { let height = 20 ; /...
  • 向量vector(1)

    2018-08-15 16:25:56
    目录   ...1.2.3 Vector模板类 1.1 从数组到向量 1.1.1 抽象数据类型与数据结构 封装 : 将数据项与相关的操作结合为一个整体,并将其从外部的可见性划分为若干等级,从而将数据结构...
  • 前,中,后缀表达式

    2019-05-22 18:51:53
    前缀表达式,中缀表达式,后缀表达式都是四则运算的表达方式,用以四则运算表达式求值,即数学表达式的求值。比如一个简单的数学表达式 (1+2)-(3+4) 这是我们常见的数学表达式类型 即中缀表达式 把这个表达式转化...
  • 后缀数组模板

    千次阅读 2015-08-21 18:28:07
    重新回味了一下后缀数组,还是太弱了…… 描述一下代码中的个数组 cc数组 计数排序用 x[I] 表示 以i开头的后缀按第一关键字排序的排名 y[I] 表示 按第二关键字排序的排名为i的后缀开始的下标 height[I] 表示 ...
  • 后缀表达式只能计算小于10的计算,同事不能包含负数 关键知识点: 1、后缀表达式使用的是字符串 2、借助的工具是栈stack 3、计算规则:数字村栈,符号从栈取两数,后数在前。 编辑器:Devc++ 代码如下: #include&...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 31,420
精华内容 12,568
关键字:

后缀vector