「琐记」字符串复习

📅 Last Updated: 2021-01-19
📊 Word Count: 185
⏱️ Estimated Reading Time: 1 minutes
📄 PDF 📝 Source

后缀数组的一次复习和整理，大部分精简自oi-wiki。

「琐记」字符串复习

SA 后缀数组

整理自 OI-Wiki.

应用

两字串最长公共前缀长度

min⁡{ height⁡[ rk⁡[i]+1,rk⁡[j] ] } \min\{\ \operatorname{height}[\ \operatorname{rk}[i] + 1, \operatorname{rk}[j]\ ]\ \}

比较字串大小关系

不妨设：A=S[a..b],B=S[c..d]A=S[a..b], B=S[c..d]

A<B  ⟺  {∣A∣<∣B∣,∣LCP(A,B)∣≥min⁡(∣A∣,∣B∣)rk⁡[a]<rk⁡[b],otherwise A < B \iff \left\{ \begin{array}{lcll} |A| & < & |B|, & |\mathbb{LCP}(A,B)| \ge \min(|A|,|B|) \\ \operatorname{rk}[a] & < & \operatorname{rk}[b], & \text{otherwise} \end{array} \right.

不同子串的数目

n(n+1)2−∑i=2nheight⁡[i] \frac{n (n + 1)}{2} - \sum_{i=2}^{n}\operatorname{height}[i]

出现至少 kk 次的子串 最大长度

如果某个子串出现了 kk 次，那么一定有连续（后缀排序后）kk 个后缀的 LCP\mathbb{LCP} 是其超串。 max⁡i{min⁡j=i+1i+k{height⁡[j]}} \max_{i}\{ \min_{j=i + 1}^{i + k}\{\operatorname{height}[j]\} \}

最长 不重叠出现两个次以上的子串

考虑二分一个值 ∣S∣|S| 表示子串长度。 考虑根据 ∣S∣|S| 把 HeightHeight 数组断成若干段。每一段内的 height⁡\operatorname{height} 的值都 ≥∣S∣\ge |S| ，检查每一段内的所有值的下标，判断是否重复。

「NOI2015」品酒大会

如果从大到小枚举 rr ，后缀排好序后，合法的串一定挨在一起，并且随着 rr 的减小，合法的区间会扩大、合并。

方案和最大值都好维护，同时维护最大值、次大值/最小值、次小值（存在负数），就可以在每次合并的过程中更新答案。

最大、次大、最小和次小不好维护…

  • 可能某个值不存在，不能使用 -1 表示不存在，可以考虑特殊化一下，特别定义某个值表示不存在，不是很可能冲突。
  • 合并的时候讨论比较麻烦，只需要考虑把这些数字都放入一个 vector ，排序去重后一一取出即可，可以避免讨论。
「AHOI2013」 差异

给出长度为 nn 的字符串 SS ，TiT_i 表示从字符 ii 开始的后缀，求： ∑1≤i≤j≤n∣Ti∣+∣Tj∣−2∣LCP(Ti,Tj)∣ \sum_{1 \le i \le j \le n}\limits{ |T_i| + |T_j| - 2 |\mathbb{LCP}(T_i, T_j)| }

因为∣LCP(Ti,Tj)∣|\mathbb{LCP}(T_i, T_j)| 直接对应后缀排序里的值，考虑对这个值单调栈求一下取值为其的区间，算贡献即可。

模板

const int _ = 1e6 + 100;
int sa[_], rk[_], ht[_];
void Suffix_Array(char *S, int n){
    static int oldrk[_], cnt[_], id[_], px[_];
    int m = max(n, 300), i, p, T, k;
    for(i = 1; i <= n; i++) cnt[rk[i] = S[i]] ++;
    for(i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for(i = n; i >= 1; i--) sa[cnt[rk[i]] -- ] = i;
    for(T = 1; T <= n; T <<= 1){
        memset(cnt, 0, sizeof(int) * (m + 5));
        memcpy(id, sa, sizeof(int) * (n + 5));
        for(i = 1; i <= n; i++) cnt[px[i] = rk[id[i] + T]] ++;
        for(i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
        for(i = n; i >= 1; i--) sa[cnt[px[i]] --] = id[i];
        
        memset(cnt, 0, sizeof(int) * (m + 5));
        memcpy(id, sa, sizeof(int) * (n + 5));
        for(i = 1; i <= n; i++) cnt[px[i] = rk[id[i]]]++;
        for(i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
        for(i = n; i >= 1; i--) sa[cnt[px[i]] -- ] = id[i];
        
        memcpy(oldrk, rk, sizeof(int) * (n + 5));
        for(p = 0, i = 1; i <= n; i++){
            if(oldrk[sa[i]] == oldrk[sa[i - 1]]
            && oldrk[sa[i] + T] == oldrk[sa[i - 1] + T])
                 rk[sa[i]] = p;
            else rk[sa[i]] = ++p;
        }
        if(p == n) break;
    }
    for(k = 0, i = 1; i <= n; i++){
        if(k) k--;
        while(S[i + k] == S[sa[rk[i] - 1] + k] && k <= n) k++;
        ht[rk[i]] = k;
    }
}

📚 Version History

Source Code Change History
v1
🔗 Source Hash: 44092d4e1e914c5bb4c70aedff3751e8f1efacbdd5f9888ee3e0ff4c8519a67d
Build Logs 
Build Log - Filtered
================================================

📋 Information:
• Path information has been filtered for privacy protection
• File names are preserved for debugging purposes  
• All build status and error messages are kept intact

🔍 Filter Rules:
• /absolute/path/file.ext → .../file.ext
• /home/username → .../[user]
• /tmp/files → .../[temp]
• /usr/share/packages → .../[system]

================================================

html log:
CMD: ['pandoc', '-s', 'cache/oi-blog_「琐记」字符串复习.md', '--filter', 'pandoc-crossref', '--filter', 'pandoc-katex', '--template=cache/pandoc_html_template.html', '-o', 'cache.../oi-blog_「琐记」字符串复习.md.html', '--metadata', '--verbose', '--highlight-style=tango']
STDOUT: 
STDERR: WARNING: pandoc-crossref was compiled with pandoc 3.6.2 but is being run through 3.6.4. This is not supported. Strange things may (and likely will) happen silently.

====================================================================================================
pdf log:
CMD: ['pandoc', '-s', 'cache.../d5fed03593.pdf.md', '-o', 'cache/d5fed03593.pdf', '-H', 'static/pandoc.header.tex', '--pdf-engine=xelatex', '--verbose']
STDOUT: 
STDERR: [INFO] Loaded static.../pandoc.header.tex from static.../pandoc.header.tex
[INFO] Not rendering RawBlock (Format "html") ""
[INFO] [makePDF] Temp dir:
  .../[temp]
[INFO] [makePDF] Command line:
  xelatex "-halt-on-error" "-interaction" "nonstopmode" "-output-directory" ".../[temp] ".../[temp]
[INFO] [makePDF] Relevant environment variables:
  ("TEXINPUTS",".../[temp]
  ("TEXMFOUTPUT",".../[temp]
  ("SHELL","/bin/bash")
  ("PWD",".../[user]/projects/blog")
  ("HOME",".../[user]
  ("LANG","zh_CN.UTF-8")
  ("PATH",".../[user]/.local/bin:.../[user]/.cargo/bin:.../[user]/miniconda3/envs/myblog/bin:.../[user]/miniconda3/condabin:.../[temp]
[INFO] [makePDF] Source:
  % Options for packages loaded elsewhere
  \PassOptionsToPackage{unicode}{hyperref}
  \PassOptionsToPackage{hyphens}{url}
  \PassOptionsToPackage{space}{xeCJK}
  \documentclass[
  ]{article}
  \usepackage{xcolor}
  \usepackage[a4paper,margin=2cm]{geometry}
  \usepackage{amsmath,amssymb}
  \setcounter{secnumdepth}{-\maxdimen} % remove section numbering
  \usepackage{iftex}
  \ifPDFTeX
    \usepackage[T1]{fontenc}
    \usepackage[utf8]{inputenc}
    \usepackage{textcomp} % provide euro and other symbols
  \else % if luatex or xetex
    \usepackage{unicode-math} % this also loads fontspec
    \defaultfontfeatures{Scale=MatchLowercase}
    \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
  \fi
  \usepackage{lmodern}
  \ifPDFTeX\else
    % xetex/luatex font selection
    \setmainfont[]{Latin Modern Roman}
    \ifXeTeX
      \usepackage{xeCJK}
      \setCJKmainfont[]{AR PL UKai CN}
    \fi
    \ifLuaTeX
      \usepackage[]{luatexja-fontspec}
      \setmainjfont[]{AR PL UKai CN}
    \fi
  \fi
  % Use upquote if available, for straight quotes in verbatim environments
  \IfFileExists{upquote.sty}{\usepackage{upquote}}{}
  \IfFileExists{microtype.sty}{% use microtype if available
    \usepackage[]{microtype}
    \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
  }{}
  \usepackage{setspace}
  \makeatletter
  \@ifundefined{KOMAClassName}{% if non-KOMA class
    \IfFileExists{parskip.sty}{%
      \usepackage{parskip}
    }{% else
      \setlength{\parindent}{0pt}
      \setlength{\parskip}{6pt plus 2pt minus 1pt}}
  }{% if KOMA class
    \KOMAoptions{parskip=half}}
  \makeatother
  \usepackage{color}
  \usepackage{fancyvrb}
  \newcommand{\VerbBar}{|}
  \newcommand{\VERB}{\Verb[commandchars=\\\{\}]}
  \DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
  % Add ',fontsize=\small' for more characters per line
  \newenvironment{Shaded}{}{}
  \newcommand{\AlertTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
  \newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.49,0.56,0.16}{#1}}
  \newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
  \newcommand{\BuiltInTok}[1]{\textcolor[rgb]{0.00,0.50,0.00}{#1}}
  \newcommand{\CharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\CommentTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textit{#1}}}
  \newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.53,0.00,0.00}{#1}}
  \newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
  \newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.56,0.13,0.00}{#1}}
  \newcommand{\DecValTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
  \newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.73,0.13,0.13}{\textit{#1}}}
  \newcommand{\ErrorTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
  \newcommand{\ExtensionTok}[1]{#1}
  \newcommand{\FloatTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
  \newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.02,0.16,0.49}{#1}}
  \newcommand{\ImportTok}[1]{\textcolor[rgb]{0.00,0.50,0.00}{\textbf{#1}}}
  \newcommand{\InformationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
  \newcommand{\NormalTok}[1]{#1}
  \newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}}
  \newcommand{\OtherTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{#1}}
  \newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.74,0.48,0.00}{#1}}
  \newcommand{\RegionMarkerTok}[1]{#1}
  \newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.73,0.40,0.53}{#1}}
  \newcommand{\StringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\VariableTok}[1]{\textcolor[rgb]{0.10,0.09,0.49}{#1}}
  \newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\WarningTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \setlength{\emergencystretch}{3em} % prevent overfull lines
  \providecommand{\tightlist}{%
    \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
  % \usepackage{xeCJK}
  % \setCJKmainfont{AR PL UKai CN}
  % \usepackage{unicode-math}
  
  \setmathfont{Latin Modern Math}
  \usepackage{bookmark}
  \IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
  \urlstyle{same}
  \hypersetup{
    pdftitle={「琐记」字符串复习},
    pdfauthor={Jiayi Su (ShuYuMo)},
    hidelinks,
    pdfcreator={LaTeX via pandoc}}
  
  \title{「琐记」字符串复习}
  \author{Jiayi Su (ShuYuMo)}
  \date{2021-01-19 15:35:06}
  
  \begin{document}
  \maketitle
  
  \setstretch{1.3}
  后缀数组的一次复习和整理，大部分精简自oi-wiki。
  
  \section{「琐记」字符串复习}\label{ux7410ux8bb0ux5b57ux7b26ux4e32ux590dux4e60}
  
  \subsection{SA 后缀数组}\label{sa-ux540eux7f00ux6570ux7ec4}
  
  整理自 OI-Wiki.
  
  \subsubsection{应用}\label{ux5e94ux7528}
  
  \paragraph{两字串最长公共前缀长度}\label{ux4e24ux5b57ux4e32ux6700ux957fux516cux5171ux524dux7f00ux957fux5ea6}
  
  \[
  \min\{\ \operatorname{height}[\ \operatorname{rk}[i] + 1, \operatorname{rk}[j]\ ]\ \}
  \]
  
  \subparagraph{比较字串大小关系}\label{ux6bd4ux8f83ux5b57ux4e32ux5927ux5c0fux5173ux7cfb}
  
  不妨设：\(A=S[a..b], B=S[c..d]\)
  
  \[
  A < B \iff
  \left\{
  \begin{array}{lcll}
  |A| & < & |B|, & |\mathbb{LCP}(A,B)| \ge \min(|A|,|B|) \\
  \operatorname{rk}[a] & < & \operatorname{rk}[b], & \text{otherwise}
  \end{array}
  \right.
  \]
  
  \subparagraph{不同子串的数目}\label{ux4e0dux540cux5b50ux4e32ux7684ux6570ux76ee}
  
  \[
  \frac{n (n + 1)}{2} - \sum_{i=2}^{n}\operatorname{height}[i]
  \]
  
  \subparagraph{\texorpdfstring{出现至少 \(k\) 次的子串
  最大长度}{出现至少 k 次的子串 最大长度}}\label{ux51faux73b0ux81f3ux5c11-k-ux6b21ux7684ux5b50ux4e32-ux6700ux5927ux957fux5ea6}
  
  如果某个子串出现了 \(k\) 次，那么一定有连续（后缀排序后）\(k\) 个后缀的
  \(\mathbb{LCP}\) 是其超串。 \[
  \max_{i}\{ \min_{j=i + 1}^{i + k}\{\operatorname{height}[j]\} \}
  \]
  
  \subparagraph{最长
  不重叠出现两个次以上的子串}\label{ux6700ux957f-ux4e0dux91cdux53e0ux51faux73b0ux4e24ux4e2aux6b21ux4ee5ux4e0aux7684ux5b50ux4e32}
  
  考虑二分一个值 \(|S|\) 表示子串长度。 考虑根据 \(|S|\) 把 \(Height\)
  数组断成若干段。每一段内的 \(\operatorname{height}\) 的值都 \(\ge |S|\)
  ，检查每一段内的所有值的下标，判断是否重复。
  
  \subparagraph{\texorpdfstring{\href{https://loj.ac/p/2133}{「NOI2015」品酒大会}}{「NOI2015」品酒大会}}\label{noi2015ux54c1ux9152ux5927ux4f1a}
  
  如果从大到小枚举 \(r\) ，后缀排好序后，合法的串一定挨在一起，并且随着
  \(r\) 的减小，合法的区间会扩大、合并。
  
  方案和最大值都好维护，同时维护最大值、次大值/最小值、次小值（存在负数），就可以在每次合并的过程中更新答案。
  
  最大、次大、最小和次小不好维护…
  
  \begin{itemize}
  \tightlist
  \item
    可能某个值不存在，不能使用 -1
    表示不存在，可以考虑特殊化一下，特别定义某个值表示不存在，不是很可能冲突。
  \item
    合并的时候讨论比较麻烦，只需要考虑把这些数字都放入一个 vector
    ，排序去重后一一取出即可，可以避免讨论。
  \end{itemize}
  
  \subparagraph{\texorpdfstring{\href{https://loj.ac/p/2377}{「AHOI2013」
  差异}}{「AHOI2013」 差异}}\label{ahoi2013-ux5deeux5f02}
  
  给出长度为 \(n\) 的字符串 \(S\) ，\(T_i\) 表示从字符 \(i\)
  开始的后缀，求： \[
  \sum_{1 \le i \le j \le n}\limits{ |T_i| + |T_j| - 2 |\mathbb{LCP}(T_i, T_j)| }
  \]
  
  因为\(|\mathbb{LCP}(T_i, T_j)|\)
  直接对应后缀排序里的值，考虑对这个值单调栈求一下取值为其的区间，算贡献即可。
  
  \subsubsection{模板}\label{ux6a21ux677f}
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \AttributeTok{const} \DataTypeTok{int}\NormalTok{ \_ }\OperatorTok{=} \FloatTok{1e6} \OperatorTok{+} \DecValTok{100}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ sa}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ rk}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ ht}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \DataTypeTok{void}\NormalTok{ Suffix\_Array}\OperatorTok{(}\DataTypeTok{char} \OperatorTok{*}\NormalTok{S}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ n}\OperatorTok{)\{}
      \AttributeTok{static} \DataTypeTok{int}\NormalTok{ oldrk}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ cnt}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ id}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ px}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
      \DataTypeTok{int}\NormalTok{ m }\OperatorTok{=}\NormalTok{ max}\OperatorTok{(}\NormalTok{n}\OperatorTok{,} \DecValTok{300}\OperatorTok{),}\NormalTok{ i}\OperatorTok{,}\NormalTok{ p}\OperatorTok{,}\NormalTok{ T}\OperatorTok{,}\NormalTok{ k}\OperatorTok{;}
      \ControlFlowTok{for}\OperatorTok{(}\NormalTok{i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ cnt}\OperatorTok{[}\NormalTok{rk}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=}\NormalTok{ S}\OperatorTok{[}\NormalTok{i}\OperatorTok{]]} \OperatorTok{++;}
      \ControlFlowTok{for}\OperatorTok{(}\NormalTok{i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ m}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ cnt}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{+=}\NormalTok{ cnt}\OperatorTok{[}\NormalTok{i }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{];}
      \ControlFlowTok{for}\OperatorTok{(}\NormalTok{i }\OperatorTok{=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textgreater{}=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i}\OperatorTok{{-}{-})}\NormalTok{ sa}\OperatorTok{[}\NormalTok{cnt}\OperatorTok{[}\NormalTok{rk}\OperatorTok{[}\NormalTok{i}\OperatorTok{]]} \OperatorTok{{-}{-}} \OperatorTok{]} \OperatorTok{=}\NormalTok{ i}\OperatorTok{;}
      \ControlFlowTok{for}\OperatorTok{(}\NormalTok{T }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ T }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ T }\OperatorTok{\textless{}\textless{}=} \DecValTok{1}\OperatorTok{)\{}
  \NormalTok{        memset}\OperatorTok{(}\NormalTok{cnt}\OperatorTok{,} \DecValTok{0}\OperatorTok{,} \KeywordTok{sizeof}\OperatorTok{(}\DataTypeTok{int}\OperatorTok{)} \OperatorTok{*} \OperatorTok{(}\NormalTok{m }\OperatorTok{+} \DecValTok{5}\OperatorTok{));}
  \NormalTok{        memcpy}\OperatorTok{(}\NormalTok{id}\OperatorTok{,}\NormalTok{ sa}\OperatorTok{,} \KeywordTok{sizeof}\OperatorTok{(}\DataTypeTok{int}\OperatorTok{)} \OperatorTok{*} \OperatorTok{(}\NormalTok{n }\OperatorTok{+} \DecValTok{5}\OperatorTok{));}
          \ControlFlowTok{for}\OperatorTok{(}\NormalTok{i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ cnt}\OperatorTok{[}\NormalTok{px}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=}\NormalTok{ rk}\OperatorTok{[}\NormalTok{id}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{+}\NormalTok{ T}\OperatorTok{]]} \OperatorTok{++;}
          \ControlFlowTok{for}\OperatorTok{(}\NormalTok{i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ m}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ cnt}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{+=}\NormalTok{ cnt}\OperatorTok{[}\NormalTok{i }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{];}
          \ControlFlowTok{for}\OperatorTok{(}\NormalTok{i }\OperatorTok{=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textgreater{}=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i}\OperatorTok{{-}{-})}\NormalTok{ sa}\OperatorTok{[}\NormalTok{cnt}\OperatorTok{[}\NormalTok{px}\OperatorTok{[}\NormalTok{i}\OperatorTok{]]} \OperatorTok{{-}{-}]} \OperatorTok{=}\NormalTok{ id}\OperatorTok{[}\NormalTok{i}\OperatorTok{];}
          
  \NormalTok{        memset}\OperatorTok{(}\NormalTok{cnt}\OperatorTok{,} \DecValTok{0}\OperatorTok{,} \KeywordTok{sizeof}\OperatorTok{(}\DataTypeTok{int}\OperatorTok{)} \OperatorTok{*} \OperatorTok{(}\NormalTok{m }\OperatorTok{+} \DecValTok{5}\OperatorTok{));}
  \NormalTok{        memcpy}\OperatorTok{(}\NormalTok{id}\OperatorTok{,}\NormalTok{ sa}\OperatorTok{,} \KeywordTok{sizeof}\OperatorTok{(}\DataTypeTok{int}\OperatorTok{)} \OperatorTok{*} \OperatorTok{(}\NormalTok{n }\OperatorTok{+} \DecValTok{5}\OperatorTok{));}
          \ControlFlowTok{for}\OperatorTok{(}\NormalTok{i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ cnt}\OperatorTok{[}\NormalTok{px}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=}\NormalTok{ rk}\OperatorTok{[}\NormalTok{id}\OperatorTok{[}\NormalTok{i}\OperatorTok{]]]++;}
          \ControlFlowTok{for}\OperatorTok{(}\NormalTok{i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ m}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ cnt}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{+=}\NormalTok{ cnt}\OperatorTok{[}\NormalTok{i }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{];}
          \ControlFlowTok{for}\OperatorTok{(}\NormalTok{i }\OperatorTok{=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textgreater{}=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i}\OperatorTok{{-}{-})}\NormalTok{ sa}\OperatorTok{[}\NormalTok{cnt}\OperatorTok{[}\NormalTok{px}\OperatorTok{[}\NormalTok{i}\OperatorTok{]]} \OperatorTok{{-}{-}} \OperatorTok{]} \OperatorTok{=}\NormalTok{ id}\OperatorTok{[}\NormalTok{i}\OperatorTok{];}
          
  \NormalTok{        memcpy}\OperatorTok{(}\NormalTok{oldrk}\OperatorTok{,}\NormalTok{ rk}\OperatorTok{,} \KeywordTok{sizeof}\OperatorTok{(}\DataTypeTok{int}\OperatorTok{)} \OperatorTok{*} \OperatorTok{(}\NormalTok{n }\OperatorTok{+} \DecValTok{5}\OperatorTok{));}
          \ControlFlowTok{for}\OperatorTok{(}\NormalTok{p }\OperatorTok{=} \DecValTok{0}\OperatorTok{,}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)\{}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{oldrk}\OperatorTok{[}\NormalTok{sa}\OperatorTok{[}\NormalTok{i}\OperatorTok{]]} \OperatorTok{==}\NormalTok{ oldrk}\OperatorTok{[}\NormalTok{sa}\OperatorTok{[}\NormalTok{i }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{]]}
              \OperatorTok{\&\&}\NormalTok{ oldrk}\OperatorTok{[}\NormalTok{sa}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{+}\NormalTok{ T}\OperatorTok{]} \OperatorTok{==}\NormalTok{ oldrk}\OperatorTok{[}\NormalTok{sa}\OperatorTok{[}\NormalTok{i }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{]} \OperatorTok{+}\NormalTok{ T}\OperatorTok{])}
  \NormalTok{                 rk}\OperatorTok{[}\NormalTok{sa}\OperatorTok{[}\NormalTok{i}\OperatorTok{]]} \OperatorTok{=}\NormalTok{ p}\OperatorTok{;}
              \ControlFlowTok{else}\NormalTok{ rk}\OperatorTok{[}\NormalTok{sa}\OperatorTok{[}\NormalTok{i}\OperatorTok{]]} \OperatorTok{=} \OperatorTok{++}\NormalTok{p}\OperatorTok{;}
          \OperatorTok{\}}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{p }\OperatorTok{==}\NormalTok{ n}\OperatorTok{)} \ControlFlowTok{break}\OperatorTok{;}
      \OperatorTok{\}}
      \ControlFlowTok{for}\OperatorTok{(}\NormalTok{k }\OperatorTok{=} \DecValTok{0}\OperatorTok{,}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)\{}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{k}\OperatorTok{)}\NormalTok{ k}\OperatorTok{{-}{-};}
          \ControlFlowTok{while}\OperatorTok{(}\NormalTok{S}\OperatorTok{[}\NormalTok{i }\OperatorTok{+}\NormalTok{ k}\OperatorTok{]} \OperatorTok{==}\NormalTok{ S}\OperatorTok{[}\NormalTok{sa}\OperatorTok{[}\NormalTok{rk}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{{-}} \DecValTok{1}\OperatorTok{]} \OperatorTok{+}\NormalTok{ k}\OperatorTok{]} \OperatorTok{\&\&}\NormalTok{ k }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{)}\NormalTok{ k}\OperatorTok{++;}
  \NormalTok{        ht}\OperatorTok{[}\NormalTok{rk}\OperatorTok{[}\NormalTok{i}\OperatorTok{]]} \OperatorTok{=}\NormalTok{ k}\OperatorTok{;}
      \OperatorTok{\}}
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  
  \end{document}
[INFO] [makePDF] LaTeX run number 1
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../fancyvrb.sty)
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty
  (.../infwarerr.sty)))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  No file input.aux.
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  
  Package hyperref Warning: Rerun to get /PageLabels entry.
  
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 116.
  
  [1]
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  [2] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
  
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
  
   )
  Output written on .../input.pdf (2 pages).
  Transcript written on .../input.log.
[INFO] [makePDF] Rerun needed
  Package hyperref Warning: Rerun to get /PageLabels entry.
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
[INFO] [makePDF] LaTeX run number 2
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../fancyvrb.sty)
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty
  (.../infwarerr.sty)))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  (.../input.aux)
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 116.
  
  [1]
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  [2] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
   )
  Output written on .../input.pdf (2 pages).
  Transcript written on .../input.log.