拉格朗日乘数法

标准形式

\begin{aligned}
\text{minimize\ } &f\\
\text{s.t.\ }&g=0
\end{aligned}

等价于

\text{minimize\ } f+\lambda g

不等式形式

\begin{aligned}
\text{minimize\ } &f\\
\text{s.t.\ }g\le 0
\end{aligned}

等价于

\begin{aligned}
\text{minimize}_x\ \text{maximize}_\lambda
\ &f+\lambda g\\
\text{s.t.\ }&\lambda\ge 0
\end{aligned}

对偶为

\begin{aligned}
\text{maximize}_\lambda
\ \text{minimize}_x\ &f+\lambda g\\
\text{s.t.\ }&\lambda\ge 0
\end{aligned}

胡扯SAIS

对于每一个后缀\text{suffix}(i),当\text{suffix}(i) < \text{suffix}(i + 1)时,是S型后缀,否则为L型后缀。
显然,\text{suffix}(i)S型后缀的充要条件为:
S_i < S_{i+1}S_i=S_{i + 1}\text{suffix}(i + 1)S型后缀。由此可以倒着一遍把每个后缀的类型推出来。为了方便处理,在字符串末尾加一个极小的字符,并且令只包含这一个字符的后缀类型为S型。
对于满足\text{suffix}(i-1)L\text{suffix}(i)S的后缀,记为LMS(Leftmost-S)后缀,并且记相邻两个LMS后缀之间(左右端点都包含)的子串为LMS子串。
popoqqq举例

p o p o q q q #
L S L S L L L S
* * *

LMS子串为opooqqq##
LMS子串排好字典序并标号,得到一个新的串。在当前例子中,LMS子串排序之后#opooqqq#,依次标号为0,1,2并且替换到原串的对应位置,得到的就是1,2,0。在这个新串中,后缀的排序,就是每个后缀在原串的左端点对应的LMS后缀的顺序。比如,在当前例子中,1,2,0的后缀排序之后为01,2,02,0,对应回原串,代表这三个LMS后缀的顺序为#opoqqq#oqqq#
得到LMS子串压成的新串之后就可以递归了,现在就考虑在已知LMS后缀的顺序的情况下如何求出所有后缀的顺序,也就是整个算法的精髓——诱导排序。
对于首字母相同的所有后缀,在最终的排序序列中,一定是先出现所有L型后缀,然后出现所有S型后缀。因为,对于S_i=S_j,\text{suffix}(i)\in \text{S-Type},\text{suffix}(j)\in \text{L-Type},一定有,\text{suffix}(i)>\text{suffix}(j)
证明:如果S_i=S_{i+1}S_j=S_{j+1},那么可以比较\text{suffix}(i+1),\text{suffix}(j+1)。否则,一定有S_i < S_{i+1}S_j>S_{j+1},可以推出结论。

对于每个首字母,维护两个桶,分别用于存储以此为首字母的LS型后缀。
首先,将LMS后缀按顺序放在S型桶内,在同一个桶内放的具体位置无所谓(?),只要保持有序就好了。
然后依次对于所有的字符,先遍历S型桶,再遍历L型桶,如果桶中的\text{suffix}(i)满足\text{suffix}(i-1)L型,就将\text{suffix}(i-1)放到对应的L型桶中。所有的L型后缀都会被按照顺序依次插入到L型的桶内。
L型后缀都有序了,那么按照类似的操作可以再将S型后缀都依次插入桶中。
最终就排好了顺序。

还有LMS子串的排序没有解决,其思路也是使用诱导排序。做法是在一开始将LMS后缀按照任意顺序插入到对应S型桶内,诱导完之后LMS后缀相对之间就是有序的了。正确性还没咋理解,先坑着…

const int XN=1e6+11;

std::vector<int> SAIS(std::vector<int> const &s,int sig) {
    int n=s.size();
    std::vector<bool> st(n);
    std::vector<int> sa(n),cnt(sig),lp(sig),sp(sig);

    auto Induce=[&]() {
        for(int i=0;i<sig;++i) {
            lp[i]=i?cnt[i-1]:0;
            sp[i]=cnt[i]-1;
        }
        for(int i=0;i<n;++i)
            if(sa[i]>0 && !st[sa[i]-1])
                sa[lp[s[sa[i]-1]]++]=sa[i]-1;
        for(int i=n-1;i>0;--i)
            if(sa[i]>0 && st[sa[i]-1])
                sa[sp[s[sa[i]-1]]--]=sa[i]-1;
    };

    st[n-1]=1;
    for(int i=n-2;i>=0;--i)
        st[i]=s[i]<s[i+1] || (s[i]==s[i+1] && st[i+1]);
    for(int i=0;i<n;cnt[s[i++]]++);
    for(int i=1;i<sig;cnt[i]+=cnt[i-1],++i);
    for(int i=0;i<sig;sp[i]=cnt[i]-1,++i);
    std::fill(sa.begin(),sa.end(),0);
    std::vector<int> lms,id(n,-1);
    for(int i=1;i<n;++i)
        if(!st[i-1] && st[i]) {
            id[i]=lms.size();
            lms.push_back(sa[sp[s[i]]--]=i);
        }
    Induce();
    int c=0;
    static int t[XN];
    for(int i=0,j,k=-1;i<n;++i)
        if((j=id[sa[i]])!=-1) {
            t[j]=k!=-1 && std::equal(s.begin()+lms[j],s.begin()+lms[j+1],s.begin()+lms[k])?c-1:c++;
            k=j;
        }

    std::vector<int> sa1(c);
    if(c==(int)lms.size())
        for(int i=0;i<c;sa1[t[i]]=i,++i);
    else 
        sa1=SAIS(std::vector<int>(t,t+lms.size()),c);
    for(int i=0;i<sig;sp[i]=cnt[i]-1,++i);
    std::fill(sa.begin(),sa.end(),0);
    for(int i=lms.size()-1;i>=0;--i)
        sa[sp[s[lms[sa1[i]]]]--]=lms[sa1[i]];
    Induce();
    return sa;
}

参考

for_each,generate,transform

std::for_each

template<class InputIterator, class Function>
  Function for_each(InputIterator first, InputIterator last, Function fn)
{
  while (first!=last) {
    fn (*first);
    ++first;
  }
  return fn;      // or, since C++11: return move(fn);
}

std::generate

template <class ForwardIterator, class Generator>
  void generate ( ForwardIterator first, ForwardIterator last, Generator gen )
{
  while (first != last) {
    *first = gen();
    ++first;
  }
}

std::transform

template <class InputIterator, class OutputIterator, class UnaryOperator>
  OutputIterator transform (InputIterator first1, InputIterator last1,
                            OutputIterator result, UnaryOperator op)
{
  while (first1 != last1) {
    *result = op(*first1);  // or: *result=binary_op(*first1,*first2++);
    ++result; ++first1;
  }
  return result;
}