首页 > 其他分享 >字符串入门指南

字符串入门指南

时间：2024-05-10 15:24:08浏览次数：21  
标签：指南 入门 int height 后缀 字符串 sa id rk

前言

此文章带领入门基础字符串，内容从 KMP 到 SA，其中包含算法文章推荐/算法讲解，经典题目的讲解。

带 ！号的题是基础例题，带 * 号的是推荐首先完成的题（有一定启发性的）。

本题单以每种字符串算法为大结构。

manacher

!P3805 【模板】manacher

好的博客

code

#include<bits/stdc++.h>
using namespace std;
const int N=2.2*1e7;
char s[N];
int n,p[N];
void build()
{
	char c[N];
	scanf("%s",c+1);
	int len=strlen(c+1);
	s[++n]='@';s[++n]='#';
	for(int i=1;i<=len;i++)	s[++n]=c[i],s[++n]='#';	
	s[++n]='!';
}
int main()
{
	build();
	int mid=0,mr=0,ans=0;
	for(int i=2;i<n;i++)	
	{
		if(i<=mr)	p[i]=min(p[mid*2-i],mr-i+1);
		else p[i]=1;
		while(s[i+p[i]]==s[i-p[i]])	++p[i];
		if(p[i]+i>mr)	mr=p[i]+i-1,mid=i;
		ans=max(ans,p[i]);	
	}
	printf("%d\n",ans-1);
	return 0;
}

例题

P3501 [POI2010] ANT-Antisymmetry

就是把两字符相等换成两字符相反。

*P4555 [国家集训队] 最长双回文串

枚举两个回文串的分隔点，在 manacher 中记录两个数组：\(L[i]\)，\(R[i]\)。分别表示以此点为末尾的左边的串的最大长度，以此点为开头的右边的串的最大长度。

但 manacher 求出的是最长回文串，而中间小的字串没有记录到，所以还要在递归求解一下：

\[L[i]=max(L[i],l[i+2]-2) \]

\[R[i]=max(R[i],R[i-2]-2) \]

P6216 回文匹配

KMP/ex-KMP

!模板 KMP

好的讲解：KMP算法详解

code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char a[N],b[N];
int p[N];
int main()
{
	scanf("%s",a+1);scanf("%s",b+1);
	int la=strlen(a+1),lb=strlen(b+1);
	// 预处理 p[] /nxt[] 数组
	p[1]=0;
	int j=0;
	for(int i=2;i<=lb;i++)
	{
		while(j&&b[j+1]!=b[i])	j=p[j];
		if(b[j+1]==b[i])	j++;
		p[i]=j; 
	} 
	// 匹配
	j=0;
	for(int i=1;i<=la;i++)
	{
		while(j&&b[j+1]!=a[i])	j=p[j];
		if(b[j+1]==a[i])	j++;
		if(j==lb)
		{
			printf("%d\n",i-lb+1);
			j=p[j];
		}
	}
	for(int i=1;i<=lb;i++)	printf("%d ",p[i]);
	return 0;
}

!模板 exKMP

exKMP 模拟器

好记忆的 exKMP 模板。

#include<bits/stdc++.h>
using namespace std;
const int N=2e7+10;
char a[N],b[N];
int la,lb;
int z[N],p[N];
void get_Z()
{
	z[1]=lb;
	for(int i=2,l=0,r=0;i<=lb;i++)
	{
		if(i<=r)	z[i]=min(z[i-l+1],r-i+1);
		while(i+z[i]<=lb&&b[z[i]+i]==b[z[i]+1])	++z[i];
		if(i+z[i]-1>r)	r=i+z[i]-1,l=i;
	}
//	for(int i=1;i<=lb;i++)	cout<<z[i]<<" ";	cout<<endl;
}
int main()
{
	scanf("%s",a+1);scanf("%s",b+1);
	la=strlen(a+1),lb=strlen(b+1);
	get_Z(); 
	for(int i=1,l=0,r=0;i<=la;i++)
	{
		if(i<=r)	p[i]=min(z[i-l+1],r-i+1);
		while(i+p[i]<=la&&b[p[i]+1]==a[p[i]+i])	p[i]++;
		if(i+p[i]-1>r)	r=i+p[i]-1,l=i;
	}
//	for(int i=1;i<=la;i++)	cout<<p[i]<<" ";	cout<<endl;
	long long ans1=0,ans2=0;
	for(int i=1;i<=lb;i++)	ans1^=1ll*i*(z[i]+1);
	for(int i=1;i<=la;i++)	ans2^=1ll*i*(p[i]+1);
	printf("%lld\n%lld",ans1,ans2);
	return 0;
}

例题

*KMP 求解有关周期类问题

P4391 [BOI2009] Radio Transmission 无线传输

最短周期：\(n-nxt[n]\)。

证明：

我们知道 \(nxt\) 数组求的是最长的公共前后缀。

如下图：

img

蓝色的与红色的两个字串相同，并为最长的公共前后缀。

橙色与红1相同，红1与蓝1相同，所以橙色与蓝1相同，依次类推，可证橙色一定是字符串的一个周期。

而 \(nxt\) 数组求的是最长的公共前后缀，橙色区段一定是最短周期。

双倍经验：Power Strings

P3435 [POI2006] OKR-Periods of Words

很好的利用了 \(nxt\) 数组的定义。

先阐述一下题目意思：定义一个 \(b\) 字符串，它是 \(a\) 的一个真字串。然后把这个 \(b\) 字串复制一遍接在原来那个字串后面，如果 \(a\) 是它的字串则称 \(b\) 是 \(a\) 的周期。求 \(a\) 的每个前缀的最长周期的和。

就以整个 \(a\) 字串为例。

img

我们分为两种情况：

  1. 字符串的 \(nxt\) 长度小于这个字符串长度的一半。

先只看那一个红色的字串。

两个紫色的字串为红色大串的最长公共前后缀。

黑色框中的字串就为一个周期，把它设为 \(b\)。

看下面的灰色的串就是复制后的 \(b\) 串，因为两个紫色的字串相同，显然红串为灰串的字串。

  1. 字符串的 \(nxt\) 长度小于这个字符串长度的一半。

现在看最大的黑串。

红色的字串与蓝色的字串相同，为最长公共前后缀；

但我们套用上一个的结论似乎不成立，因为橙色的串复制后根本达不到黑串的长度。

但我们可以发现如果用整串减去红串的最长公共前后缀，为黑串的一个周期。

因为紫串等于三个绿串，所以粉框中的字串就为黑串的周期。

但此时求出的不一定的最小周期，所以我们一直 j=nxt[j] 直到：nxt[j]==0 时为止。

这样即求出最小周期，也把上面两种情况合并了。

如果每一个串都跳的话时间复杂度太高，所以递推 \(nxt\) 数组，分摊下来就是 \(O(n)\) 的复杂度。

code:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
char s[N];
int p[N], n;
int main()
{
    scanf("%d", &n);
    scanf("%s", s + 1);
    p[1] = 0;
    for (int i = 2, j = 0; i <= n; i++)
    {
        while (j && s[j + 1] != s[i])
            j = p[j];
        if (s[j + 1] == s[i])
            j++;
        p[i] = j;
    }
    // for (int i = 1; i <= n; i++)
    //     cout << p[i] << " ";
    // cout << endl;
    int j = 2;
    long long ans = 0;
    for (int i = 2; i <= n; i++)
    {
        j = i;
        while (p[j])
            j = p[j];
        if (p[i])
            p[i] = j;
        ans += i - j;
    }
    printf("%lld", ans);
    return 0;
}

失配树

!P5829 【模板】失配树

只要充分了解了 \(nxt\) 数组，与会求 LCA，那此知识点十分好理解，同上一题都需要不停的向前跳。

上题是单个跳，还可以路径压缩，那这题就是两个一起跳，直到跳到同一深度，这里就和求 LCA 一样了。（注：LCA 不能是给定的两个结点）。

code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m;
char s[N];
int f[N][22], dep[N], d[N];
int lca(int u, int v)
{
    if (dep[u] < dep[v])
        swap(u, v);
    for (int i = 20; i >= 0; i--)
        if (dep[f[u][i]] >= dep[v])
            u = f[u][i];
    // if (u == v)  这里求的 LCA 不能是给的两个结点
    //     return u;
    for (int i = 20; i >= 0; i--)
    {
        if (f[u][i] != f[v][i])
            u = f[u][i], v = f[v][i];
    }
    return f[u][0];
}
int main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1);
    f[1][0] = 0, dep[1] = 1;
    for (int i = 2, j = 0; i <= n; i++)
    {
        while (j && s[j + 1] != s[i])
            j = f[j][0];
        if (s[j + 1] == s[i])
            j++;
        f[i][0] = j;
        dep[i] = dep[j] + 1;
    }
    // for (int i = 1; i <= n; i++)
    //     cout << f[i][0] << " ";
    //    cout << endl;
    for (int i = 1; i <= 20; i++)
        for (int j = 1; j <= n; j++)
            f[j][i] = f[f[j][i - 1]][i - 1];
    scanf("%d", &m);
    while (m--)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        printf("%d\n", lca(u, v));
    }
    return 0;
}

P2375 [NOI2014] 动物园

有了失配树的想法，此题很容易想到倍增优化，先跳到比 \(len/2\) 大的位置，然后再跳到零，记录后者跳的次数即可。

记得倍增时把小的那一位放前面，寻址快，优化常数。

但此题正解是 \(O(n)\) 的递归优化，有点像（P3435）。

我们知道每次每次都重新跳容易卡成 \(O(n^2)\)，我们将递归用的变量 \(j\) 的值不更新，这样，求完了 \(i\) 的答案以后，\(j\) 的位置一定在 \(i/2\) 的左边。

当然，\(j\) 的位置不一定是下一个前缀的最大公共前后缀的字串，所以可以再次跳 \(nxt\)。

AC 自动机

算法及模板

注：此算法是建立在会 Trie 的前提下。

P3808 AC 自动机（简单版）

P3796 AC 自动机（简单版 II）

P5357 【模板】AC 自动机

好的学习博客：yyb的博客，其实 oi wiki 的图也做得不错。

补充：

  1. fail 指针指向所有模式串的前缀中匹配当前状态的最长后缀（有点像 KMP）。

  2. 这里把 Trie 树改成了 Trie 图， fail 指针跳转的路径做了压缩（就像并查集的路径压缩），使得本来需要跳很多次 fail 指针变成跳一次。

第一题 code:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
struct node
{
    int end, fail, son[30];
} tr[N];
int n, cnt = 1;
void build_tree()
{
    char s[N];
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    int u = 1;
    for (int i = 1; i <= len; i++)
    {
        int v = s[i] - 'a';
        if (!tr[u].son[v])
            tr[u].son[v] = ++cnt;
        u = tr[u].son[v];
        //        cout << u << " " << s[i] << endl;
    }
    tr[u].end++;
}
void get_fail()
{
    for (int i = 0; i < 26; i++)
        tr[0].son[i] = 1;
    queue<int> q;
    q.push(1);
    tr[1].fail = 0;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = 0; i < 26; i++)
        {

            int v = tr[u].son[i];
            if (!v)
                tr[u].son[i] = tr[tr[u].fail].son[i];
            else
            {
                tr[v].fail = tr[tr[u].fail].son[i];
                q.push(v);
            }
        }
    }
}
void ac_ask()
{
    char s[N];
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    int u = 1, ans = 0;
    for (int i = 1; i <= len; i++)
    {
        int v = s[i] - 'a';
        int k = tr[u].son[v];
        while (k > 1 && tr[k].end != -1)
        {
            ans += tr[k].end;
            tr[k].end = -1;
            k = tr[k].fail;
        }
        u = tr[u].son[v];
    }
    printf("%d\n", ans);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        build_tree();

    get_fail();
    ac_ask();
    return 0;
}

第三题拓扑优化：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 6;
int n, cnt, sum[N], in[N], mp[N];
struct node
{
    int son[27], end, fail, ans;
    void init()
    {
        memset(son, 0, sizeof son);
        ans = end = fail = 0;
    }
} tr[N];
char s[N];
void build_tree(int id)
{
    scanf("%s", s + 1);
    int len = strlen(s + 1), u = 1;
    for (int i = 1; i <= len; i++)
    {
        int v = s[i] - 'a';
        if (!tr[u].son[v])
            tr[u].son[v] = ++cnt;
        u = tr[u].son[v];
    }
    if (!tr[u].end)
        tr[u].end = id;
    mp[id] = tr[u].end;
}
void get_fail()
{
    for (int i = 0; i < 26; i++)
        tr[0].son[i] = 1;
    queue<int> q;
    q.push(1);
    tr[1].fail = 0;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = 0; i < 26; i++)
        {

            int v = tr[u].son[i];
            if (!v)
                tr[u].son[i] = tr[tr[u].fail].son[i];
            else
            {
                tr[v].fail = tr[tr[u].fail].son[i];
                in[tr[v].fail]++;
                q.push(v);
            }
        }
    }
}
void ac_ask()
{
    char c[N];
    scanf("%s", c + 1);
    int len = strlen(c + 1), u = 1;
    for (int i = 1; i <= len; i++)
    {
        int v = c[i] - 'a';
        u = tr[u].son[v];
        tr[u].ans++;
    }
}
void topu()
{
    queue<int> q;
    for (int i = 1; i <= cnt; i++)
        if (!in[i])
            q.push(i);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        int v = tr[u].fail;
        sum[tr[u].end] += tr[u].ans;
        tr[v].ans += tr[u].ans;
        in[v]--;
        if (!in[v])
            q.push(v);
    }
}
int main()
{
    cnt = 1;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        build_tree(i);
    get_fail();
    ac_ask();
    topu();
    for (int i = 1; i <= n; i++)
        printf("%d\n", sum[mp[i]]);
    return 0;
}

例题

P3966 [TJOI2013] 单词

其实就是模板。

模板中记录次数是文本串的字符的 \(ans++\)，而此题所有都是文本串，所以在建 Trie 树时，每个结点的 \(ans++\) 即可。

void build_tree(int id)
{
    scanf("%s", s + 1);
    int len = strlen(s + 1), u = 1;
    for (int i = 1; i <= len; i++)
    {
        int v = s[i] - 'a';
        c[++tot] = s[i];
        if (!tr[u].son[v])
            tr[u].son[v] = ++cnt;
        u = tr[u].son[v];
        tr[u].ans++;    //添加的地方。
    }
    if (!tr[u].end)
        tr[u].end = id;
    mp[id] = tr[u].end;
}

P3121 [USACO15FEB] Censoring G

有些时候只是用了建好的新 Trie 图。

这个新的 Trie 图每个结点都连了 26 条边，所以在最后字符串匹配时能保证 \(O(n)\) 的复杂度，就可以判断每一个模式串（每个串都不同）是否在文本串中出现过。

而 fail 既完成了新的 Trie 图的建立，也可以在匹配阶段完成每个模式串出现的出现（如同模板）。

在 get_fail 时也用了前面求过的 fail，就如同 KMP 的 nxt 的求法。

此题只用建好 Trie 图，然后用栈维护，一旦找到就 pop，最后栈里剩下就是要求的字符串。

P2444 [POI2000] 病毒

先建好 Trie 图，在图上做 dfs，不走有病毒标志的结点。

因为找的串是无限循环的字符串，就是要找到循环节，所以找到一个环即为找到循环节，就返回 ture。

注意：如果一个结点的 fail 有标志，那它也应打上标记，因为根据 fail 的定义，fail 结点的前缀为当前结点的最长公共后缀，既然 fail 结点是个完整的字符串，那说明此节点所在字符串包含 fail 结点的字符串，显然是不符条件，所以也打上标记。

上面两道题都用的是 Trie 图。

P2414 [NOI2011] 阿狸的打字机

很好的一道题。

  1. 40分做法：

  • 最暴力的方法：跑 \(m\) 次 KMP。

  • 建一个 AC 自动机，每次询问时一直跳 fail，找 \(y\) 串中出现了多少次 \(x\) 串。

  1. 70分做法

上面的40分做法一直在跳 fail，所以想到建棵失配树。

树一般都是从上往下的，所以我们反向，就是求 \(x\) 串的子树中出现了多少 \(y\) 串。

这里可以用树状数组，线段树等数据结构，但树状数组常数小又好写，此题肯定用它了。

先 dfs 一下求一下 dfn，可以知道一个子树的 dfn 一定是连续的，当出现 \(y\) 串就 \(+1\)，这里可以用树状数组解决。

如果是 \(y\)串 是散的，复杂度与上面的方法一样，所以我们按 \(y\) 排序，这样每次 dfs 就可以除了 \(y\) 相同的询问。

时间复杂度：\(O(n^2+mlogm)\)。

  1. 100分做法

上面的方法还是跑了许多重复的子树，考虑在线加点与删点。

当枚举到一个结点时 \(+1\)，回溯时 \(-1\)，这样就可以完美通过此题。

此题的细节：

  • 第二次 dfs 时用旧的的 Trie 树。

  • 注意建 Trie 树的时间复杂度。

以上的题目用到了 AC 自动机的两种用途：使用新建的 Trie 图与用 fail 数组建立失配树。

后缀数组（SA）

算法讲解

注 ：此节完全引用机房大佬 Comentropy 的文章（个人觉得写的好），由于他未发表，所以把文章引用于此。

基数排序就是先按第一关键字排序，相同时比较第二关键字，再相同时比较第三关键字，依次类推。

后缀数组分为两部分，第一部分是后缀数组本身，求解后缀数组来表示后缀的字典序排名，第二部分将会使用后缀数组将他们和子串关联起来。

这一部分参照了 OI Wiki 的相关内容，特此注明。

再次提醒默认下标从 \(1\) 开始，约定“后缀 \(i\)” 是以第 \(i\) 个字符开头的后缀，记作 \(suff(i)\)。特殊的情况中需要突出的使用 C++ 中的下标记法 \(a[i]\) 替代数学记法 \(a_i\)。

后缀数组

后缀数组 (Suffix Array) 主要关系到两个数组，\(sa\) 和 \(rk\)。

  • \(sa_i\) 表示后缀排序后第 \(i\) 小的后缀编号，这就是所谓后缀数组。
  • \(rk_i\) 表示后缀 \(i\) 的排名。

满足一个重要性质：\(sa[rk_i]=rk[sa_i]=i\)。

我们很显然有 \(O(n^2\log{n})\) 的做法，即暴力将后缀排序，注意单次比较时间是 \(O(n)\) 级的。

很显然，排序具有可合并性，所以我们可以进行倍增：具体地，以上一轮每个后缀的排名为第一关键字，以长度 \(k\) 之后的后缀排名为第二关键字进行排序，倍增 \(k\) 即可。注意初始化 \(k=0\) 时的排名，然后从 \(k=1\) 开始倍增。特别注意：如果后缀 \(i\) 的后继，即后缀 \(i+k\) 没有字符，则默认排名最小。如果使用快排，则我们需要 \(O(n\log^2{n})\) 的时间。但是由于关键字较少，我们可以使用 基数排序，使得排序时间降为线性，整体时间降至 \(O(n\log{n})\)。这在绝大情况下都够用了。以下是倍增示意图（源自 oi-wiki 转载的国家集训队论文）。

img

算法除了基数排序的部分，大致实现基本都很简单。以下为大致实现：

  1. 预处理出 \(k=1\) 时的排名（注意，请对倍增有清晰的了解，我们本质上是在从 \(k\) 转移到 \(2k\) 的状态，并不是在处理 \(k=0\)）。然后开始倍增字串长度 \(k\)，即所有后缀 \(i\) 目前只处理了 \(s[i,i+k-1]\)。
  2. 先对于第二关键字进行排序，处理出第二关键字有序的对应后缀开头 \(id_i\)。
  3. 然后对第一关键字进行排序，若两个关键字相同，则暂时共用一个排名，否则比较。这一步，我们其实已经把上一轮的第一关键字排好了，直接按顺序比较即可。
  4. 如此处理直到 \(k>n\).

结合代码具体阐释（模板题 P3809）：

int n=strlen(s+1),m=122;
for(int i=1;i<=n;i++)	cnt[rk[i]=s[i]]++;
for(int i=1;i<=m;i++)	cnt[i]+=cnt[i-1];
for(int i=n;i>=1;i--)	sa[cnt[rk[i]]--]=i;

这一部分是基数排序的基本操作，设值域为 \(m\)，其初值为字符 z 的 ASCII 码。然后设置初始 \(rk_i=s_i\)，并统计每个排名 \(i\) 的出现次数 \(cnt_{i}\) 并前缀和。倒序处理 \(sa\) 的目的是：越靠后假定的排名越靠后。\(cnt\) 前缀和是为了得到排名为 \(i\) 的最后的下标在何处，以此对应进 \(sa\)。

for(int k=1;k<=n;k<<=1)

倍增正常操作，目的是从 \(k\) 转移到 \(2k\)。

int num=0;
for(int i=n-k+1;i<=n;i++)
    id[++num]=i;
for(int i=1;i<=n;i++)
    if(sa[i]>k)
        id[++num]=sa[i]-k;

\(num\) 是下标，由于从 \(n-k+1\) 开始到 \(n\)，其第二关键字为空，所以它们排在最前面。并且，如果某个排名 \(i\)，其 \(sa_i>k\) 说明它可以往前推 \(k\) 位，\(sa[i]-k\) 拥有了下一个排名的第二关键字（我们在升序枚举排名，并尝试令其成为第二关键字）。这一步不重不漏的结论是显然的，留给读者思考。

for(int i=1;i<=m;i++)	cnt[i]=0;	// 按值域清空
for(int i=1;i<=n;i++)	cnt[rk[i]]++;
for(int i=1;i<=m;i++)	cnt[i]+=cnt[i-1];
for(int i=n;i>=1;i--)	sa[cnt[rk[id[i]]]--]=id[i],id[i]=0;

类似地统计第一关键字（即排名）并前缀和，而最后一行与之前不太一样。倒序地，我们获取了第二关键字排名为 \(i\) 的后缀的开头下标 \(id_i\)。我们获取 \(id_i\) 的第一关键字，即 \(rk\)。然后对第一关键字排序，注意 \(sa[\dots]\) 应当赋成 \(id_i\)（开头位置）。

我们更新完了 \(sa\)，接下来更新 \(rk\)。

std::swap(rk,id);
num=1,rk[sa[1]]=1;
for(int i=2;i<=n;i++)
    if(id[sa[i]]==id[sa[i-1]]&&id[sa[i]+k]==id[sa[i-1]+k])
        rk[sa[i]]=num;
    else
        rk[sa[i]]=++num;
if(num==n)
    break ;
m=num;

上一步已经将 \(id\) 清空，此时，交换两个数组，注意：\(id\) 此时的含义是上一轮的排名。

先赋初值，\(num\) 表示当前排名，使得 \(rk[sa[1]]=1\)。我们从 \(2\) 枚举排名 \(i\)。

如果两个关键字都相同则排名相同，否则排名不同，而注意到其实此时排名已经确定，即 \(sa_i\)，所以我们只是在处理相同的 \(rk\)，这或许会好理解一点（?。

于是完成了 \(rk\) 和 \(sa\) 的更新。同时注意到基数排序的特性——如果排名 \(n\) 个已经确定，不论第二关键字如何变动，排名都不会变动。于是 \(num=n\) 时退出循环，否则使关键字值域 \(m \leftarrow num\)。

code

#include<cstdio>
#include<cstring>
#include<algorithm>
const int N=1e6+500;
int sa[N],rk[N],id[N],cnt[N];
char s[N];
void SA(){
	int n=strlen(s+1),m=122;
	for(int i=1;i<=n;i++)	cnt[rk[i]=s[i]]++;
	for(int i=1;i<=m;i++)	cnt[i]+=cnt[i-1];
	for(int i=n;i>=1;i--)	sa[cnt[rk[i]]--]=i;
	for(int k=1;k<=n;k<<=1){
		int num=0;
		for(int i=n-k+1;i<=n;i++)
			id[++num]=i;
		for(int i=1;i<=n;i++)
			if(sa[i]>k)
				id[++num]=sa[i]-k;
		for(int i=1;i<=m;i++)	cnt[i]=0;
		for(int i=1;i<=n;i++)	cnt[rk[i]]++;
		for(int i=1;i<=m;i++)	cnt[i]+=cnt[i-1];
		for(int i=n;i>=1;i--)	sa[cnt[rk[id[i]]]--]=id[i],id[i]=0; 
		std::swap(rk,id);
		num=1,rk[sa[1]]=1;
		for(int i=2;i<=n;i++)
			if(id[sa[i]]==id[sa[i-1]]&&id[sa[i]+k]==id[sa[i-1]+k])
				rk[sa[i]]=num;
			else
				rk[sa[i]]=++num;
		if(num==n)
			break ;
		m=num;
	}
	for(int i=1;i<=n;i++)
		printf("%d ",sa[i]);
	return ;
}
int main(){
	scanf("%s",s+1);
	SA();
	return 0;
}

事实上，还有 DC3，SA-IS 的线性算法可以完成任务，这里不再介绍。

\(height\) 数组

两个字符串 \(S\) 和 \(T\) 的最长公共前缀长度是最大的 \(x(x\leq \min(\lvert S\rvert,\lvert T\rvert))\)，使得 \(S_i=T_i(\forall i, 1\leq i \leq x)\)，最长公共前缀就是 \(S[1,x]\)。

记后缀 \(i\) 和后缀 \(j\) 的最长公共前缀，LCP(Longest Common Preffix)，长度 为 \(lcp(i,j)\)。

（特别注意在做题时个别题解的表述出现了问题。）

定义 \(height[i]=lcp(sa_i,sa_{i-1})\)，即第 \(i\) 名后缀与前一名后缀的 \(LCP\) 长度，\(height[1]\) 可以视作 \(0\)。

去 \(height\) 数组需要引理：\(height[rk_i] \geq height[rk_{i-1}]-1\)，这样就可以 \(O(1)\) 转移相邻两个字符，总时间复杂度 \(O(n)\)。证明如下：

  • 由于 \(height\) 非负，所以当 \(height[rk_{i-1}]\leq 1\) 时，上式成立。以下讨论 \(height[rk_{i-1}]> 1\) 的情况。

根据定义：\(height[rk_{i-1}]=lcp(sa[rk_{i-1}],sa[rk_{i-1}-1])>1\)。

由上式：设后缀 \(i-1\) 和 \(sa[rk_{i-1}-1]\) 长度为 \(height[rk_{i-1}]\) 的 LCP，为字符串 \(aA\)，其中 \(a\) 为一个字符，\(A\) 为一个非空串。

则又可设 \(suff(i-1)=aAD\)，\(suff(sa[rk_{i-1}-1])=aAB\)，其中 \(B\) 可能为空，\(B<D\)，\(D\) 非空。

于是可以向后转移：\(suff(i)=AD\)，\(suff(sa[rk_{i-1}-1]+1)=AB\)。

又由于后缀 \(sa[rk_i-1]\) 仅比 \(sa[rk_i]\) 排名小一位，而 \(AB<AD\)，所以有：\(AB \leq suff(sa[rk_i-1]) <AD\)（由放缩原理）。

显然，\(suff(sa[rk_i-1])\) 与 \(suff(sa[rk_i])\) 有公共前缀 \(A\).

所以：\(lcp(i,sa[rk[i]-1]) \geq height[rk_{i-1}]-1\)，即 \(height[rk_i]\geq height[rk_{i-1}]-1\)，证毕。

看张图手动跑一下更好理解

img

如图中的黑色后缀(saff(\(i-1\))) 与 灰色后缀(saff(\(sa[rk_{i-1}]\))) 减去 \(a\) 的最长公共前缀为 \(b\)，

与图中的红色后缀(saff(\(i\))) 与 橙色后缀(saff(\(sa[rk_{i-1}]\))) 的最长公共前缀为 \(b\)，

由此可以实现：

for(int i=1,k=0;i<=n;i++){
    if(rk[i]==1)
        continue ;
    if(k)   k--;
    while(s[i+k]==s[sa[rk[i]-1]+k])
        k++;
    h[rk[i]]=k;
}

特别注意 \(height\) 数组的定义，匹配的是哪个数组，最后更新的应该是 \(height[rk_i]\)。

\(height\) 数组的应用

  1. 两后缀公共前缀

后缀排名为 \(i\)，\(j\) 的两个后缀的最长公共前缀长度，有 \(lcp(sa_i,sa_j)=\min\{height[i+1..j]\}\)。

这是一个较为显然的性质，称为 LCP Theorem，感性理解即可（严格证明较为麻烦）。这转化成一个 RMQ 问题。

  1. 本质不同子串个数

\(height\) 数组经常被用来处理子串问题，一个非常典型的例子就是求本质不同子串个数，例题：P2408 不同子串个数。

因为 子串就是后缀的前缀，所以我们按 后缀排名 枚举每个后缀，在前缀数中减去重复前缀。设当前枚举到了排名 \(i\) 的后缀， 由于 \(lcp(sa_i,sa_{i-1})=height[i]\)，那么对于该后缀 \(sa_i\)，前面的 每一个串 对后缀 \(sa_i\) 造成的重复前缀，长度都应当小于等于 \(height[i]\)；特别地，排名 \(i\) 和 \(i-1\) 的后缀已经有了 \(height[i]\) 个重复：所以在其串长上减去 \(height[i]\)，累计所有不重复的后缀，得到答案。

\[\begin{align} res=& \sum_{i=1}^n (n-sa[i]+1)-height[i]& \\= & \sum_{i=1}^n i -\sum_{i=1}^n height[i] & \\=&\frac{n(n+1)}{2} - \sum_{i=2}^n height[i]&\\ \end{align} \]

（如果已经理解，无需理会这句话）特别注意，我们无需管与后面的是否相重，因为我们需要计算一次出现的串，而某一重复前缀必定受到上述限制，所以这样是正确的。

  1. 比较子串大小

若要比较 \(A=s[a..b]\) 和 \(B=s[c..d]\)，那么：

  • 如果 \(lcp(a,c) \geq \min(\lvert A\rvert,\lvert B\rvert)\)，则 \(A,B\) 为前后缀关系，\(A<B\) 等价于 \(\lvert A\rvert < \lvert B\rvert\)。
  • 否则，\(A<B\)，在 LCP 中就能比较出来，等价于比较 \(rk_a<rk_c\)。

例题

P2870 [USACO07DEC] Best Cow Line G

可以把原串复制翻转一遍，接在原串后面，跑一遍 SA。

走双指针，\(l\) 在原串开头，\(r\) 在新串开头，比较 \(rk[l]\) 与 \(rk[r]\) 输出即可。

P2178 品酒大会

因为有负值调了好久。

此题又有后缀，有让求两个后缀的 lcp，那很自然的想到 SA。

跑 SA，求 height。

然后此题要求两个问，我们一个一个求。

  1. \(lcp(i,j) \ge r,r \in 1 \cdots n\) 有多少对？

此题的询问是让输出 \(1 \cdots n\) 所有的，并且 \(r\) 的二元组 一定包含 \(r+1\) 的二元组，所以想到从大到小推。

height 只求了 \(lcp(sa_i,sa_{i-1})\)，\(lcp(sa_i,sa_j)\) 就是求 \(\min\{height[i+1..j]\}\)。

我们把 \(height[i]\) 看作 \(sa[i]\) 与 \(sa[i-1]\) 连的一条边的权值。

当 \(r\) 枚举到 \(i\) 时，就把所有边权为 \(i\) 的两边的点加入一个集合，每个集合的两点都是合法的二元组。那这里很容易想到并查集。

但如果每次都把 \(1\) 到 \(n\) 枚举一遍时间会超，那把边排序，走指针就行了。

此时并查集的的每个集合中要记录 fa，size。

每合并一个集合就让 \(size[y]+=size[y]*size[x]\)。

  1. 所有满足要求的二元组中，乘积最大是多少？

有了上面的的方法只需要在每个集合中记录最大值与次大值即可。

但此题有负数，所以还要记录负数的最小值与次小值。

此题解决。

丑陋的代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 10, inf = 1e18;
int n;
int sa[N], rk[N], cnt[N], id[N];
int a[N];
pair<int, int> ans[N];
char s[N];
struct sim
{
    int val, id, to, from;
} h[N];
struct dsu
{
    int fa, pmax1, pmax2, nmin1, nmin2, siz;
    dsu()
    {
        pmax1 = pmax2 = -inf;
        nmin1 = nmin2 = inf;
    }
} bin[N];
void SA()
{
    int m = 122;
    for (int i = 1; i <= n; i++)
        cnt[rk[i] = s[i]]++;
    for (int i = 1; i <= m; i++)
        cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; i--)
        sa[cnt[rk[i]]--] = i;
    for (int k = 1; k <= n; k <<= 1)
    {
        int num = 0;
        for (int i = n - k + 1; i <= n; i++)
            id[++num] = i;
        for (int i = 1; i <= n; i++)
            if (sa[i] > k)
                id[++num] = sa[i] - k;
        for (int i = 1; i <= m; i++)
            cnt[i] = 0;
        for (int i = 1; i <= n; i++)
            cnt[rk[i]]++;
        for (int i = 1; i <= m; i++)
            cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--)
            sa[cnt[rk[id[i]]]--] = id[i];
        swap(id, rk);
        num = 1;
        rk[sa[1]] = 1;
        for (int i = 2; i <= n; i++)
        {
            if (id[sa[i]] == id[sa[i - 1]] && id[sa[i] + k] == id[sa[i - 1] + k])
                rk[sa[i]] = num;
            else
                rk[sa[i]] = ++num;
        }
        if (n == num)
            break;
        m = num;
    }
}
void get_height()
{
    for (int i = 1, k = 0; i <= n; i++)
    {
        if (rk[i] == 1)
            continue;
        if (k)
            k--;
        while (s[i + k] == s[sa[rk[i] - 1] + k])
            k++;
        h[rk[i]].val = k;
    }
}
bool cmp(sim x, sim y)
{
    return x.val > y.val;
}
int find(int x)
{
    return x == bin[x].fa ? x : (bin[x].fa = find(bin[x].fa));
}
signed main()
{
    scanf("%lld", &n);
    scanf("%s", s + 1);
    SA();
    get_height();
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for (int i = 1; i <= n; i++)
    {
        h[i].id = sa[i];
        if (i == 1)
            continue;
        h[i].from = sa[i - 1];
        h[i].to = sa[i];
    }
    sort(h + 1, h + 1 + n, cmp);
    for (int i = 1; i <= n; i++)
    {
        bin[i].fa = i;
        bin[i].siz = 1;
        if (a[i] > 0)
            bin[i].pmax1 = a[i];
        if (a[i] < 0)
            bin[i].nmin1 = a[i];
    }
    int l = 1;
    int res = -inf, num = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        while (h[l].val == i && l <= n)
        {
            int u = h[l].from, v = h[l].to;
            int x = find(u), y = find(v);
            bin[x].fa = y;
            int ss[4], yy[4];
            ss[0] = bin[y].nmin1, ss[1] = bin[y].nmin2, ss[2] = bin[x].nmin1, ss[3] = bin[x].nmin2;
            yy[0] = bin[y].pmax1, yy[1] = bin[y].pmax2, yy[2] = bin[x].pmax1, yy[3] = bin[x].pmax2;
            sort(ss, ss + 4);
            sort(yy, yy + 4);
            bin[y].pmax1 = yy[3], bin[y].pmax2 = yy[2], bin[y].nmin1 = ss[0], bin[y].nmin2 = ss[1];
            int mx1 = bin[y].pmax1, mx2 = bin[y].pmax2, mn1 = bin[y].nmin1, mn2 = bin[y].nmin2;
            if (mx1 != -inf && mx2 != -inf)
                res = max(res, 1ll * mx1 * mx2);
            if (mn1 != inf && mn2 != inf)
                res = max(res, 1ll * mn1 * mn2);
            if (mn1 != inf && mx1 != -inf)
                res = max(res, 1ll * mn1 * mx1);
            if (mn1 != inf && mx2 != -inf)
                res = max(res, 1ll * mn1 * mx2);
            if (mn2 != inf && mx1 != -inf)
                res = max(res, 1ll * mn2 * mx1);
            if (mn2 != inf && mx2 != -inf)
                res = max(res, 1ll * mn2 * mx2);
            num += bin[x].siz * bin[y].siz;
            bin[y].siz += bin[x].siz;
            ans[i].first = num;
            l++;
        }
        ans[i].second = res != -inf ? res : 0;
    }
    for (int i = 0; i < n; i++)
        printf("%lld %lld\n", ans[i].first, ans[i].second);
    return 0;
}

P4248 差异

此题还是利用：\(lcp(sa_i,sa_j)=\min\{height[i+1..j]\}\)。

定义 f 为 \(lcp(i,j),j \in 1 \cdots i-1\)。

找到第一个小于 \(height[i]\) 的 \(height[j]\)，\(f[i]=f[j]+height[i]*(i-j)\)。

此处就可以用单调栈了。

code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
char s[N];
int n, sa[N], cnt[N], id[N], rk[N], h[N], f[N];
int ans = 0;
stack<int> q;
void SA()
{
    int m = 122;
    for (int i = 1; i <= n; i++)
        cnt[rk[i] = s[i]]++;
    for (int i = 1; i <= m; i++)
        cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; i--)
        sa[cnt[rk[i]]--] = i;
    for (int k = 1; k <= n; k <<= 1)
    {
        int num = 0;
        for (int i = n - k + 1; i <= n; i++)
            id[++num] = i;
        for (int i = 1; i <= n; i++)
            if (sa[i] > k)
                id[++num] = sa[i] - k;
        for (int i = 1; i <= m; i++)
            cnt[i] = 0;
        for (int i = 1; i <= n; i++)
            cnt[rk[i]]++;
        for (int i = 1; i <= m; i++)
            cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--)
            sa[cnt[rk[id[i]]]--] = id[i];
        swap(id, rk);
        rk[sa[1]] = 1, num = 1;
        for (int i = 2; i <= n; i++)
        {
            if (id[sa[i]] == id[sa[i - 1]] && id[sa[i] + k] == id[sa[i - 1] + k])
                rk[sa[i]] = num;
            else
                rk[sa[i]] = ++num;
        }
        if (num == n)
            break;
        m = num;
    }

    int k = 0;
    for (int i = 1; i <= n; i++)
    {
        if (rk[i] == 1)
            continue;
        if (k)
            k--;
        while (s[i + k] == s[sa[rk[i] - 1] + k])
            k++;
        h[rk[i]] = k;
    }
}
signed main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1);
    SA();
    ans = (n + 1) * n / 2 * (n - 1);
    for (int i = 1; i <= n; i++)
    {
        while (!q.empty() && h[i] < h[q.top()])
            q.pop();
        if (q.empty())
            f[i] = h[i] * i;
        else
            f[i] = f[q.top()] + (i - q.top()) * h[i];
        q.push(i);
        ans -= 2 * f[i];
    }
    cout << ans << endl;
    return 0;
}

P3181 找相同字符

题意翻译就是求串 \(A\)、\(B\)，每两个后缀的 \(lcp\)。

像上题的解法，用单调栈找到第一个小于 \(height[i]\) 的 \(height[j]\)。

但此题的 f 求法有变化，后缀匹配时不能匹配到原串（\(A\) 不能找 \(A\)），所以分两次求，先求相同串 \(A\) 在 \(B\) 前面。

定义一个 sum 数组，记录哪些串属于 \(B\)，再求前缀和。

可得式子：

\(f[i]=f[q[top]]+height[i]*(sum[i-1]-sum[q[top]-1])\)

最后统计 \(A\) 串的 f。

\(B\) 在前 \(A\) 在后同理。

code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4e5 + 10;
int n;
int sa[N], rk[N], cnt[N], id[N], h[N];
char s1[N], s2[N], s[N];
int f[N], q[N], sum[N];
void SA()
{
    int m = 128;
    for (int i = 1; i <= n; i++)
        cnt[rk[i] = s[i]]++;
    for (int i = 1; i <= m; i++)
        cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; i--)
        sa[cnt[rk[i]]--] = i;
    for (int k = 1; k <= n; k <<= 1)
    {
        int num = 0;
        for (int i = n - k + 1; i <= n; i++)
            id[++num] = i;
        for (int i = 1; i <= n; i++)
            if (sa[i] > k)
                id[++num] = sa[i] - k;
        for (int i = 1; i <= m; i++)
            cnt[i] = 0;
        for (int i = 1; i <= n; i++)
            cnt[rk[i]]++;
        for (int i = 1; i <= m; i++)
            cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--)
            sa[cnt[rk[id[i]]]--] = id[i];
        swap(id, rk);
        num = 1;
        rk[sa[1]] = 1;
        for (int i = 2; i <= n; i++)
        {
            if (id[sa[i]] == id[sa[i - 1]] && id[sa[i] + k] == id[sa[i - 1] + k])
                rk[sa[i]] = num;
            else
                rk[sa[i]] = ++num;
        }
        if (n == num)
            break;
        m = num;
    }
}
void get_height()
{
    for (int i = 1, k = 0; i <= n; i++)
    {
        if (rk[i] == 1)
            continue;
        if (k)
            k--;
        while (s[i + k] == s[sa[rk[i] - 1] + k])
            k++;
        h[rk[i]] = k;
    }
}
signed main()
{
    scanf("%s", s1 + 1);
    scanf("%s", s2 + 1);
    int len1 = strlen(s1 + 1), len2 = strlen(s2 + 1);
    for (int i = 1; i <= len1; i++)
        s[i] = s1[i];
    s[len1 + 1] = '~';
    for (int i = 1; i <= len2; i++)
        s[len1 + i + 1] = s2[i];
    n = len1 + len2 + 1;
    SA();
    get_height();
    int ans = 0;
    int top = 0;
    for (int i = 1; i <= n; i++)
    {
        if (sa[i] <= len1)
            sum[i]++;
        sum[i] += sum[i - 1];
    }
    for (int i = 1; i <= n; i++)
    {
        while (top && h[i] < h[q[top]])
            top--;
        f[i] = f[q[top]] + (sum[i - 1] - sum[q[top] - 1]) * h[i];
        q[++top] = i;
        if (sa[i] > len1 + 1)
            ans += f[i];
    }
    memset(f, 0, sizeof f);
    for (int i = 1; i <= n; i++)
    {
        sum[i] = 0;
        if (sa[i] > len1 + 1)
            sum[i]++;
        sum[i] += sum[i - 1];
    }
    top = 0;
    for (int i = 1; i <= n; i++)
    {
        while (top && h[i] < h[q[top]])
            top--;
        f[i] = f[q[top]] + (sum[i - 1] - sum[q[top] - 1]) * h[i];
        q[++top] = i;
        if (sa[i] <= len1)
            ans += f[i];
    }
    printf("%lld", ans);
    return 0;
}

P1117 [NOI2016] 优秀的拆分

此题求把一个字符串构成 AABB 的方案数。

考虑枚举 AA 与 BB 的分割点，设 分割点前面的 AA 的方案数为数组 a，分割点前面的 BB 的方案数为数组 b。

现在的难点就是 a 与 b 的求法。

记两个特殊点 \(i,j\)。

如下图：

img

蓝串为 \(i,j\) 后缀的最长前缀，红串为 \(i,j\) 前缀的最长后缀，记蓝串的长度为：\(len1\)，红串的长度为：\(len2\)。

蓝红串正反跑一次 SA 可求出。

当 \(len1+len2<i-j+1\) 时，无法构成 AABB 的串。

$ len1+len2 \ge i-j+1$ 时（如图）就会出现 \(len1+len2-(i-j+1)\) 个符合 AABB 的字串。

把头尾标记下来跑一次前缀和就求出了 a，b。

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int T,h1[N],h2[N],sa[N],cnt[N],id[N],rk[10][N],a[N],b[N],st1[N][30],st2[N][30];
char s[N];
void clearr()
{
	memset(a,0,sizeof a);
	memset(b,0,sizeof b);
	memset(st1,0,sizeof st1);
	memset(st2,0,sizeof st2);
	memset(sa,0,sizeof sa);
	memset(id,0,sizeof id);

}
void SA(int idd)
{
	int m=122,n=strlen(s+1);
	for(int i=1;i<=m;i++)cnt[i]=0;
	for(int i=1;i<=n;i++)cnt[rk[idd][i]=s[i]]++;
	for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
	for(int i=n;i>=1;i--)sa[cnt[rk[idd][i]]--]=i;
	for(int k=1;k<=n;k<<=1)
	{
		int num=0;
		for(int i=n-k+1;i<=n;i++)id[++num]=i;
		for(int i=1;i<=n;i++)
		if(sa[i]>k)id[++num]=sa[i]-k;
		for(int i=1;i<=m;i++)cnt[i]=0;
		for(int i=1;i<=n;i++)cnt[rk[idd][id[i]]]++;
		for(int i=2;i<=m;i++)cnt[i]+=cnt[i-1];
		for(int i=n;i>=1;i--)sa[cnt[rk[idd][id[i]]]--]=id[i],id[i]=0;
		swap(rk[idd],id);
		rk[idd][sa[1]]=1,num=1;
		for(int i=2;i<=n;i++)
		{
			if(id[sa[i]]==id[sa[i-1]]&&id[sa[i]+k]==id[sa[i-1]+k])
			rk[idd][sa[i]]=num;
			else rk[idd][sa[i]]=++num;
		}
		if(n==num)break;
		m=num;
	}
}
int st(int a,int b,int id)
{
	int l=rk[id][a],r=rk[id][b];
	if(l>r)swap(l,r);
	l++;
	int t=log2(r-l+1);
	if(id==1)
	return min(st1[l][t],st1[r-(1<<t)+1][t]);
	if(id==2)
	return min(st2[l][t],st2[r-(1<<t)+1][t]);
}
signed main()
{
	scanf("%lld",&T);
	while(T--)
	{
		memset(rk[1],0,sizeof rk[1]);
		memset(rk[2],0,sizeof rk[2]);
		memset(h1,0,sizeof h1);
		memset(h2,0,sizeof h2);
		scanf("%s",s+1);
		int n=strlen(s+1);
		clearr();
		SA(1);
		int k=0;
		for(int i=1;i<=n;i++)
		{
			if(rk[1][i]==1)continue;
			if(k)k--;
			while(s[i+k]==s[sa[rk[1][i]-1]+k])k++;
			h1[rk[1][i]]=k;
		}

		reverse(s+1,s+1+n);
		clearr();
		SA(2);
		k=0;
		for(int i=1;i<=n;i++)
		{
			if(rk[2][i]==1)continue;
			if(k)k--;
			while(s[i+k]==s[sa[rk[2][i]-1]+k])k++;
			h2[rk[2][i]]=k;
		}
		for(int i=1;i<=n;i++)
		st1[i][0]=h1[i],st2[i][0]=h2[i];
		for(int i=1;i<=18;i++)
		for(int j=1;j+(1<<i)-1<=n;j++)
		{
			st1[j][i]=min(st1[j][i-1],st1[j+(1<<(i-1))][i-1]);
			st2[j][i]=min(st2[j][i-1],st2[j+(1<<(i-1))][i-1]);
		}
		
		for(int len=1;len<=n/2;len++)
		{
			for(int i=len;i<=n;i+=len)
			{
				int j=i+len;
				int lcp=min(len,st(i,j,1));
				int lcs=min(len-1,st(n-(i-1)+1,n-(j-1)+1,2));
				if(lcs+lcp>=len)
				{
					a[i-lcs]++,a[i-lcs+(lcp+lcs-len+1)]--;
					b[j+lcp-(lcp+lcs-len+1)]++,b[j+lcp]--;
				}
			}
		}
		for(int i=1;i<=n;i++)
		a[i]+=a[i-1],b[i]+=b[i-1];
		
		long long ans=0; 
		for(int i=1;i<n;i++)
		ans+=a[i+1]*b[i];
		cout<<ans<<endl;
	}
	return 0;
 }

标签：指南,入门,int,height,后缀,字符串,sa,id,rk
From： https://www.cnblogs.com/hutongzhou/p/18169036

相关文章

  • 洛谷题单指南-动态规划2-P3147 [USACO16OPEN] 262144 P
    原题链接：https://www.luogu.com.cn/problem/P3147题意解读：将一组数据两两相邻且相同的合并，合并成一个数值+1的数，求合并后的最大值。解题思路：考虑合并后的最大数i，其最后一次必然是由两个i-1合并而来的设dp[i][j]表示以j为左端点，合并最大值为i时的右端点的下一个位置如图：dp[i......
  • php使用mysql-text字段存取json字符串
    PHP保存时过滤掉双引号&单引号&tabfunctionformartJsonString($jsonString=''){ $jsonString=str_replace("'","",$jsonString); $jsonString=str_replace('\"',"",$jsonString); $jsonString=st......
  • 字符串截取
    2024-05-10 11:14:48LOCATE(substr,str)：返回子串substr在字符串str中第一次出现的位置，如果字符substr在字符串str中不存在，则返回0；POSITION(substrINstr)：返回子串substr在字符串str中第一次出现的位置，如果字符substr在字符串str中不存在，与LOCATE函数作用相同；LEF......
  • curl 的用法指南
    简介curl是常用的命令行工具，用来请求Web服务器。它的名字就是客户端（client）的URL工具的意思。它的功能非常强大，命令行参数多达几十种。如果熟练的话，完全可以取代Postman这一类的图形界面工具。本文介绍它的主要命令行参数，作为日常的参考，方便查阅。内容主要翻译自《curl......
  • Go语言：统计字符串相关的函数
    统计字符串相关的函数：（1）统计字符串的长度，按字节进行统计（注意：UTF-8编码是Go语言默认的字符编码，汉字通常占用3个字节。）len（str）备注：因为len是Go语言的内置函数，所以不需要导包，直接使用就可以了。 (2)字符串遍历方式一：利用键值循环：for-rangefori,value:=rangestr{f......
  • XML Schema（XSD）详解：定义 XML 文档结构合法性的完整指南
    XMLSchema描述了XML文档的结构。XMLSchema语言也称为XMLSchemaDefinition（XSD）。 <?xmlversion="1.0"?> <xs:schemaxmlns:xs="http://www.w3.org/2001/XMLSchema">   <xs:elementname="note"> <xs:compl......
  • Vue入门到关门之Vue3学习
    一、常用API注意：本文项目均使用脚手架为Vite1、setup函数（1）介绍如果在项目中使用配置项API，那么写起来就和vue2的写法是一样的；但是如果在项目中写的是组合式API，那么组件中所用到的：数据、方法等等，均要配置在setup中。此外，setup()钩子也是在组件中使用组合式API的入口，通常只在......
  • XML Schema（XSD）详解：定义 XML 文档结构合法性的完整指南
    XMLSchema描述了XML文档的结构。XMLSchema语言也称为XMLSchemaDefinition（XSD）。<?xmlversion="1.0"?><xs:schemaxmlns:xs="http://www.w3.org/2001/XMLSchema"><xs:elementname="note"><xs:complexType><x......
  • Vue入门到关门之Vue2高级用法
    一、在vue项目中使用ref属性ref属性是Vue.js中用于获取对DOM元素或组件实例的引用的属性。通过在普通标签上或组件上添加ref属性，我们可以在JavaScript代码中使用this.$refs.xxx来访问对应的DOM元素或组件实例。放在普通标签上，通过this.$refs.名字---》取到的是do......
  • Vue入门到关门之Vue3项目创建
    一、vue3介绍1、为什么要学习vue3？vue3的变化：首先vue3完全兼容vue2，但是vue3不建议用vue2的写法；其次，vue3拥抱TypeScript，之前vue2使用的JavaScript，ts完全兼容js最后之前学的vue2是配置项api，而vue3是组合式apioptionsAPI(旧)=>compositionAPI（新）,效果:代码组织更方便了,逻辑......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99