NOIP复赛复习(十四)字符串算法巩固与提高

一、Trie树

1.定义

通过字符串建成一棵树,这棵树的节点个数一定是最少的。例如:4个字符串"ab","abc","bd","dda"对应的trie树如下:

NOIP复赛复习(十四)字符串算法巩固与提高-少儿编程网

其中红色节点表示存在一个字符串是以这个点结尾的。

一个性质:在树上,两个点u,v满足u是v的祖先,那么u代表的字符串一定是v代表的字符串的前缀。

2.Trie树的插入

可以从根节点出发,每次沿着要走的字符串往下走,若没有则建立新节点。

假如所有字符串的长度之和为n,构建这棵trie树的时间复杂度为O(n)。
int root=1;
int cnt=1;
int p[i][j];//表示从i这个节点沿着j这个字符走,能走到哪个点,走不到就是0
char s[];//存储字符串
for(int i=1;i<=n;i++)
{
scanf("%s",s);
int len=strlen(s);
int now=root;//now表示走到的当前节点,now的初始值为根节点
for(intj=0;j<len;j++)
{
if(p[now][s[j]]>0){
now=p[now][s[j]];//如果能沿着j节点往下走,直接往下走
}
else{
pow[now][s[j]]=++cnt;
now=p[now][s[j]];
}
}
v[now]++;//记录now这个节点被访问的次数
}

3.Trie树的查询

可以看出trie树中每个节点表示其中一个字符串的前缀,在做题过程中往往通过这个性质来得到较好的时间复杂度。

4.一个例题

给定n个互不相同的串,求存在多少对数(i,j)(共n2对)满足第i个串是第j个串的前缀。

所有串的长度之和≤500000。

解题:根据性质,“在树上,两个点u,v满足u是v的祖先,那么u代表的字符串一定是v代表的字符串的前缀”。

我们要满足一个串是另一个串的前缀,也就是说,在trie树上,这个串对应的位置是另一个串对应的位置的祖先。

构建这棵trie树,然后我们枚举每个红色点,它对答案的贡献是以它为根的子树中红色节点的个数之和。这个东西可以在一开始遍历这棵树预处理出来!

时间复杂度是线性的。
void dfs(int x)
{
if(v[x]) sum[x]++;
for(chari='a';i<='z';i++)
{
if(p[x][i])//从当前x沿着i这个字符走还能往下走
{
dfs(p[x][i]);//往下走
sum[x]+=sum[p[x][i]];//累加贡献sum
}
}
}
dfs(1);//从根节点开始

5.USACO的某题

给定n个串,重排字符之间的大小关系,问哪些串有可能成为字典序最小的串。

所有字符串的长度之和<=100000。

例如,有一个字符串,里面只有'a'~'z'这些字符,默认地,'a'是最小的,'z'是最大的。但是我们可以重新定义字符间的大小关系,比如这样:b<c<d<y<x<z,从而我们对于一些字符串,就按照我们新定义的大小关系来比较字典序大小。

举个栗子:

三个字符串"aab","aba","baa",总共只出现了两个字符'a'和'b',所以字符间的大小关系要么是a<b要么是a>b,假设a<b,则第一个串"aab"就是字典序最小的串;假设b<a,则第三个串"baa"就是字典序最小的串,但是对于第二个串,无论我们怎么定义字符间的大小关系,都不可能成为三个字符串中字典序最小的。

解题:首先对这n个串构建trie树,之后对每个串,从根走向它,这个路程中遇到的所有兄弟在字典序下都比它大。

对于每个串,从前往后,直接确定这个字符的大小关系,判断是否是字典序最小。

以下两个串都是有可能成为字典序最小的串的:

abcd…xyza

abcd…xyzb

所以有:u是v的前缀,则v一定不是字典序最小的串。

现在问题来了:对于每个串,在什么条件下,是字典序最小的??

来个栗子:有一些字符串("aabc","aac","aad","ac","adb","aabb"),构造trie树如下:

NOIP复赛复习(十四)字符串算法巩固与提高-少儿编程网

对于"aabc"这个串,往下遍历:

从深度为2的那一层,我们可以得到:a<c,a<d;

从深度为3的那一层,我们可以得到:b<c,b<d;

从深度为4的那一层,我们还可以得到:c<b。

综上所述:我们得到了一堆的关系:a<c,a<d;b<c,b<d;c<b,容易看出,这些关系是存在矛盾的,所以无解->"aabc"是不可能成为字典序最小的串。

所以要想有解,这一堆的关系必须满足两个条件:①不存在矛盾②不存在环

总的来说,就是判断这一堆的关系是否存在拓扑序!

最多有26×26个大小关系,而最多有100000个字符串,所以时间复杂度最大为:O(26×26×100000)。

二、KMP算法

给定两个字符串A,B,判断T是否为S的子串(变式:寻找子串B在串A中的位置)。

要求一个O(|A|+|B|)的做法。

通常称A为目标串(或主串),B为模式串。

算法过程:

我们假设串A的长度为n,串B的长度为m,每个字符串的开头下标默认为1。

NOIP复赛复习(十四)字符串算法巩固与提高-少儿编程网

定义两个变量i和j,这两个变量共同表示:A[i-j+1~i]与B[1~j]均匹配,即:A中以第i个字符结尾的、长度为j的字符串,和B从头开始长度为j的字符串完全匹配。

NOIP复赛复习(十四)字符串算法巩固与提高-少儿编程网

继续往下匹配:如果i+1和j+1不匹配。

NOIP复赛复习(十四)字符串算法巩固与提高-少儿编程网

现在,就是用到了KMP算法的核心:它对这一情况的处理方式是减少j,就相当于将子串向右平移。

平移的目的是为了让“A[i-j+1~i]与B[1~j]均匹配”这个条件重新满足。

NOIP复赛复习(十四)字符串算法巩固与提高-少儿编程网

在上图中,j一直减小到了0,因为向右平移的过程中,始终不能让这个条件满足(最右边"?"部分已经越界)

但有时候,将j减少一点点之后,是可以重新满足条件的,例如:

NOIP复赛复习(十四)字符串算法巩固与提高-少儿编程网

那么我们将j从7减小到4时,有:

NOIP复赛复习(十四)字符串算法巩固与提高-少儿编程网

这样就可以完全匹配啦!但是后面还有没有匹配的机会我们就不管了,至少我们已经保证A[4~7]和B[1~4]完全匹配上了。

现在考虑一个问题:我们每次把j减小1(一位一位地平移B字符串),这样太慢了,我们在这里预处理一个next[]数组,表示当j匹配不下去的时候,我们可以把j减少到next[j],继续尝试匹配。

预处理过程:让j自己和自己匹配一下,一旦匹配发现B[k-m+1~k] 和 B[1~m] 匹配,则说明在A与B匹配过程中,j等于k匹配不下去时,j可以尝试减小到m。

过程如下:

NOIP复赛复习(十四)字符串算法巩固与提高-少儿编程网


NOIP复赛复习(十四)字符串算法巩固与提高-少儿编程网

一些代码:
/*核心内容*/
for(int i=1,j=0;i<=n;i++)
{
while(j&&B[j+1]!= A[i]) j=next[j];
if(B[j+1]==A[i]) j++;
if(j==m)
{
printf("%dn", i-j+1);//输出找到的"B字串在 A中位置"
//如果要求的是出现次数,这里也有可能是ans++什么的
j=next[j];//让循环进行下去
}
}
for(int i=2,j=0;i<=m;i++)/*预处理next[]数组*/
{
while(j&&B[j+1]!=B[i]) j=next[j];
if(B[j+1]==B[i]) j++;
next[i]=j;
}

经典例题:Blue jeans(POJ 3080)

给定m个串,求字典序最小的公共子串。找一个串,使得这个串是所有串的子串,并且字典序最小。

m≤10,每个串的长度≤60.

解题思路:一个串,如果是所有串的子串,那么肯定是第一个串的子串。

枚举所有子串,复杂度为60*60。

验证其它串是否包含这个子串,复杂度为10*60。

每次更新答案即可。

时间复杂度为:O(603×10)

经典例题:Seek the Name,Seek the Fame(POJ 2752)

给定一个字符串S,求所有既是S的前缀又是S的后缀的子串,从小到大输出这些串的长度。

|S|<=500000。

N为字符串S的长度。

解题思路:

回到KMP算法,我们令P[j]表示找最大的数x,使得B中位置是1~x的字符与j-x+1~j的字符完全相同,也就是上面讲的KMP算法中的next[]。

考虑P[|S|]的意义,也就是最大的前缀等于后缀的长度(不包括其本身)。

那P[P[|S|]]就是次大的。

因此所有P[P[…P[|S|]]]就是答案了,一直这样递归下去就可以找到答案。

或者用Hash来做,这样更容易想到也比较方便,但效率没有KMP高。

三、AC自动机

有n个模式串,长度之和是|T|,有一个主串,长度是|S|,问哪些模式串是这个主串的子串(或者有多少个模式串在主串中出现过)?

解法一:直接跑n次KMP算法,时间复杂度:O(n×|S|)。

解法二:AC自动机,时间复杂度:O(|T|+|S|),对于n个串,构建trie树,在trie树上做KMP。

在这里我来详解一下AC自动机啊~

首先我们定义一个指针,叫做“失配指针”或者“失败指针”,在KMP算法中,这个失配指针就是next[]数组,同样地在AC自动机中,在trie树上也定义一个失配指针与此类似但不完全相同。

失配指针:假设一个节点k的失配指针指向j,那么k、j满足性质:设根节点root到j的距离为n,则从k以上的第n个节点到k这个节点所组成的长度为n的单词,与根节点root到j所组成的单词完全相同。

如下图:

NOIP复赛复习(十四)字符串算法巩固与提高-少儿编程网

单词"she"中的'e'的失配指针指向的是单词"her"中的'e',因为红框中的部分是完全一样的。

然后,问题来了,我们该怎样处理这个失配指针呢?其实我们可以用BFS就很方便地解决了。

处理过程:让和根节点直接相连的节点的失配指针指向根节点,对于其他节点(假设为a),设这个节点上的字母为ch,沿着a的父亲b的失配指针走,一直走到一个节点c,c的儿子中也有字母为ch的节点d,然后把a节点的失配指针指向c节点的儿子d(因为d的字母也为ch),如果一直走到了根节点都没找到,那就把失配指针指向根节点。

最开始,我们把根节点加入队列(根节点的失败指针显然指向自己),这以后我们每处理一个点,就把它的所有儿子加入队列,直到搞完。

这样我们就得到了一棵带有失配指针的trie树了,接下来正式介绍AC自动机工作原理!

AC自动机原理:对于一棵trie树,我们用黄色表示一个单词(某个模式串)的末尾,也就是说从根节点走到一个黄色的点,就组成一个“单词”,如下图:

NOIP复赛复习(十四)字符串算法巩固与提高-少儿编程网

一开始,trie树中有一个指针t1指向根节点root,将这n个模式串合并为一个模式主串,模式主串中有一个指针t2指向这个模式主串的串头。

接下来进行类似KMP算法的操作:如果t2指向的字母,是trie树中,t1指向的节点的儿子,那么把t2+1,t1改为那个儿子的编号,否则t1顺这当前节点的失配指针往上找,直到t2是t1的一个儿子,或者t1指向根为止。

如果t1经过了一个黄色的点,那么以这个点结尾的单词就算出现过了(这个模式串已经在主串中出现了),或者如果t1所在的点可以沿着失配指针走到一个黄色的点,那么以那个黄色的点为结尾的单词就算出现过了(这个模式串已经在主串中出现了),记录答案即可。

经典例题:假装是字符串的题——正则表达式

给定一个字符串,判断其是否为合法的正则表达式。

一个正则表达式定义为:

①0是正则表达式,1也是正则表达式。

②P和Q都是正则表达式,则PQ也是正则表达式。

③P是正则表达式,则(P)是正则表达式

④P是正则表达式,则P*也是正则表达式

⑤P和Q都是正则表达式,则P|Q是正则表达式

举个栗子:

010101101*

(11|0*)*

以上都是都是正则表达式

|S|<=100

解题思路:令dp[i][j]表示第i个字符到第j个字符能否组成正则表达式,分5种情况进行转移就可以了。

四、随机算法

①随机生成一棵树:
for(int i=2;i<=n;i++)/*随机生成一棵树*/
{
cout<<rand()%(i-1)+1<<' '<<i<<endl;
}//深度为lgn

②随机生成一棵长毛的链:
/*随机生成一棵长毛的链:1~n/2*/
for(int i=2;i<=n/2;i++) cout<<i-1<<''i<<endl;
for(int i=n/2+1;i<=n;i++) cout<<rand()%(i-1)+1<<''<<endl;

③给你一张图,生成一张图:
/*给你一张图,生成一张图,10万个点,20万条边 */
map<long long,int> mp;
for(int i=1;i<=200000;i++)
{
int A=rand()%n+1;
int B=rand()%n+1;
while(A==B||mp[1ll*A*100005+B])
{
A=rand()%n+1;
B=rand()%n+1;
}
mp[1ll*A*10005+B]=1;
cout<<A<<''<<B<<endl;
}

④随机生成一个连通图:

先生成一棵树,这棵树上的边是一定存在的,在随机其他的边。

本文链接:NOIP复赛复习(十四)字符串算法巩固与提高

转载声明:本站文章若无特别说明,皆为原创,转载请注明来源:少儿编程网,谢谢!^^


*文章为作者独立观点,不代表少儿编程网立场
发表评论

坐等沙发
相关文章
NOIP少年丨黄子桉:不骄不躁不傲慢不强求
NOIP少年丨黄子桉:不骄不躁不傲慢不强求
为什么越来越多家长选择信息学竞赛?
为什么越来越多家长选择信息学竞赛?
孩子学完各个阶段的编程课程能够参加哪些比赛?
孩子学完各个阶段的编程课程能够参加哪…
信息学竞赛必经之路–NOIP(内含2018报名方式说明)
信息学竞赛必经之路–NOIP(内含20…
我的孩子从来没有接触过编程,0基础能不能学?
我的孩子从来没有接触过编程,0基础能不…
新手想参加信息学竞赛NOIP ,如何入门进阶?
新手想参加信息学竞赛NOIP ,如何入门进…
NOIP2017 作者
NOI官网发布了2017年全国青少年信息学奥林匹克联赛(NOIP2017)的报名通知。NOIP2017将于2017年10月及11月分别举行初赛和复赛,有意向参加比赛的考生,即日起至10月10日可报名。