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

字符串入门指南

时间:2024-05-10 15:24:08浏览次数:23  
标签:指南 入门 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\),其初值为字符 zASCII 码。然后设置初始 \(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;
}

事实上,还有 DC3SA-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\) 枚举一遍时间会超,那把边排序,走指针就行了。

此时并查集的的每个集合中要记录 fasize

每合并一个集合就让 \(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

现在的难点就是 ab 的求法。

记两个特殊点 \(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 的字串。

把头尾标记下来跑一次前缀和就求出了 ab

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(新),效果:代码组织更方便了,逻辑......