[关闭]
@XLM 2017-10-20T01:17:49.000000Z 字数 5468 阅读 371

复杂语法的末日——字符串总结

学习 总结

在计算机处理的所有数据中，最自然也最易于被人们理解的大概就是字符串了。
但正所谓世间无有两全法，最易于人们理解的却更不易被计算机理解。事实上，计算机在处理字符数据时也是直接转换为整型来处理的。
由于用户的输入字符一般非常的肆无忌惮，所以字符串往往意味着大量数据和线性或是log要求。
这样，一大批算法及数据结构应运而生。
然而本文只愿意介绍几个

匹配

在一个庞大的数据里寻找一些关键点并不容易，利用计算机找特定词语的存在位置不失为提取关键信息的一个好办法。这就需要我们的字符串匹配算法。
怎么匹配呢？

Bruce Force

第一种算法实际上，就是暴力，只不过有了一个好听的名字。
算法的思想是这样的，此处输入图片的描述
如图所示，S为需要被匹配的串，我们叫他目标串或原始串；T则是用来匹配的串，我们叫它模式串。
最简单的想法，就是从S[0]和T[0]开始逐位比较，失配则后移一位
此处输入图片的描述
以此类推直到匹配成功或是目标串结束。
这种匹配方式，在S和P串均为随机字符的时候表现很好，但是对于算法竞赛中充满恶意的出题人，这个算法在故意出的数据中会被卡到O(nm)，其中n,m为两个字符串的长度。
不够用啊。

Hash Table

我们一次次的比较不可以，那么我们一段一段的比较呢？
考虑把一个子串压为一个数，然后对于原串的每一个长度与模式串相等的串计算hash值，对于模式串再进行hash值计算，然后比较hash值即可。
那么hash值怎么算？
emmmm

  1. char t[maxn],s[maxn];
  2. int basic=7,mod=19260817;//暴力膜一发
  3. int cy[maxn];//内存7的i次方
  4. int val_t,val_s[maxn];
  5. int len_t,len_s;
  6. int hash(int beg,int end,char *buf){
  7.     int cnt=1,pos=beg;
  8.     int ans=0;
  9.     while (pos<=end)
  10.         ans=(ans+(buf[pos++]-'a'+1)*cy[cnt++])%mod;
  11.     return ans;
  12. }//计算一个字符数组一段区间内的hash值
  14. void get_t(){
  15.     len_t=strlen(t);
  16.     val_t=hash(0,len_t-1,t);
  17. }
  19. void get_s(){
  20.     len_s=strlen(s);
  21.     val_s[0]=hash(0,len_t-1,s);//printf("%d ",val_s[0]);
  22.     for (int i=1;i<len_s-len_t+1;i++){
  23.         val_s[i]=(val_s[i-1]/7-(s[i-1]-'a'+1)+(s[i+len_t-1]-'a'+1)*cy[len_t]);
  24.     }
  25. }

但是hash有一个缺点，就是我们在压制hash值时舍弃了很多信息，这就造成了匹配不一定正确，甚至用专门的数据直接卡掉hash算法。不过由于hash的时间复杂度非常优秀，有时可以适当的用一下。

【补充】双hash

对于上面可能被卡掉的hash算法，有方法加以优化，方法也很简单，就是在hash的时候多取一个模数，比如这样

  1. const int base=11,Mod1=19260817,Mod2=9999973;

在hash的时候，取两次膜，然后比较，只有两次答案值均相等才视为相等。

  1. int hash_num1(string temp){
  2.     int len=temp.size();
  3.     int ans=0;
  4.     for (int i=0;i<len;i++){
  5.         ans=(ans*base%Mod1+temp[i]-'a')%Mod1;
  6.     }
  7.     return ans;
  8. }
  10. int hash_num2(string temp){
  11.     int len=temp.size();
  12.     int ans=0;
  13.     for (int i=0;i<len;i++){
  14.         ans=(ans*base%Mod2+temp[i]-'a')%Mod2;
  15.     }
  16.     return ans;
  17. }

这样在一定程度上提高了正确率。

KMP（其实是MP）

为了保证100%的准确，我们还是要回到字符匹配上来。
再看看上面的BF算法，我们发现我们重复进行了很多次匹配，模式串的数个位置都进行了不必要的重复匹配。
那么可不可以对模式串进行预处理减少匹配次数呢？
当然不然你以为我在写什么
KMP是Knuth-Morris-Pratt三人同时发现的算法，真正的KMP对算法本身进行了一个优化，在这里我们只说未经优化但是复杂度同样优秀的MP版（以下仍称KMP）；
再次看一下图
此处输入图片的描述
在KMP中，我们直接跳到了这一步
此处输入图片的描述
but how？

next数组
介绍重要的next(or fail)数组，这是一个用来对失配情况进行跳费的数组。
一看文主就是炉石传说死忠玩家
那么这个数组里面存的是什么东西呢，有一点拗口，叫做最长前缀后缀长度
什么鬼？
举个栗子：
假如现在有一个串abcdbcdabc，他的最长前缀后缀是一个串，这个串既是他的前缀又是他的后缀而且不是它本身，在例子串中这个最长前缀后缀就是abc
长度自然还是长度。
怎么算呢？
假设我们的串是从0开始，因为最长前缀后缀不包括本身，所以显然next[0]=0
现在，假设我们已经算出next[0]~next[i-1]现在计算next[i]
考虑next[i-1],这中储存的位置必有s[0~next[i-2]]=s[i-next[i-2]~i-1].
所以当s[next[i-1]]=s[i]时就有next[i]=next[i-1]+1
十分完美。
然而当s[next[i-1]]!=s[i]时呢？
那样就要求我们找到一个位置pos，要求0<=pos<=i&&s[0,pos-1]=s[i-pos,i]&&s[pos]=s[i]
并且在满足这些要求的情况下pos尽量大
容易想到下一个满足位置的pos值为next[next[i-1]]这时再次进行判断，不行则再次循环，直至符合条件或者next[pos]=0，计数即可。
不难搞出代码

  1. void get_next(){
  2.     len=strlen(buf);
  3.     next[0]=next[1]=0;
  4.     for (int i=1;i<len;i++){
  5.         int j=next[i];
  6.         while (j&&buf[i]!=buf[j]) j=next[j];
  7.         if (buf[i]==buf[j]) next[i+1]=j+1;
  8.         else next[i+1]=0;
  9.     }
  10. }

匹配过程
仍然从头开始匹配，考虑在i位置失配且next[i]，当前，已经匹配到了s[l~r]与t[0,i-1]这时需要回溯到next[i]继续匹配，因为根据next[i]的定义，可以得到t[0,j-1]和S[r-j+1,r]匹配，同时可知对于任何j<y<i，t[0,y]不和S[r-y,r]匹配，这样就可以保证匹配过程中不会漏掉可匹配的位置。
给出匹配代码

  1. int KMP(){
  2.     int len_2=strlen(T);
  3.     int cnt=0,j=0;
  4.     for (int i=0;i<len_2;i++){
  5.         while (j&&T[i]!=buf[j]) j=next[j];
  6.         if (buf[j]==T[i]) j++;
  7.         if (j==len) cnt++;//注意这里不能把j重置为0，因为匹配的串可能会有重复的地方
  8.     }
  9.     return cnt;//返回的是匹配成功了几次
  10. }

KMP总结
KMP（MP）算法的最坏情况是一直进行回溯，但就算这样复杂度仍然是O(n+m)，而且因为它完全没有丢失信息匹配是准确的，所以不失为一个好算法
怕是不需要你说

回文

这些算法应用的地方较小，不过因为其很巧妙，所以也可以学一发。
找最长回文子串这种问题尽管不是很常见却也是一个挑战
方法很多，一一列举

枚举子串

O(n^2)枚举枚举起点终点，对于每次枚举可以用栈或一些东西用O(n)判断是否回文
复杂度O(n^3)

中心扩展

枚举中心，分回文子串长短为奇数偶数讨论，O(n)枚举拓展
复杂度O(n^2)

正解Manacher

在算法二中，我们看到分类讨论，这样增大了常数，考虑采取这样的操作

  1. int get_buf(char *temp){
  2.     int len_temp=strlen(temp+1);
  3.     buf[0]='$';//防止越界
  4.     for (int i=1;i<=len_temp;i++){
  5.         buf[2*i]=temp[i];
  6.         buf[2*i-1]='#';//往原串中每两个字母添加一个原串绝对不会出现的符号
  7.     }
  8.     buf[2*len_temp+1]='#';
  9.     buf[2*len_temp+2]='&';//防止越界
  10.     return 2*temp+1;//返回的是新串的长度
  11. }

这样有什么好处？首先避免了奇数和偶数的分类讨论，第二又简化了操作。什么操作？待会你就知道了。
现在介绍Manacher算法所用到的额外东西：len数组
是什么
len数组里存放的是最长回文半径，就是满足回文的buf[l]-buf[r]中端点到对称轴的距离，就是r-i+1。
那么进行上面的操作的时候len[i]-1就是以i为对称轴的最长回文子串的长度。
那么len数组如何计算呢？
同样的，可以递推而来。
怎么办
在递推的过程中维护两个变量:Max_right代表当前枚举到的最长回文子串所到达的最右端的位置;pos代表搞出最长回文子串的对称轴的位置。
假设当前已经算出len[0]-len[i-1]，现要计算len[i]，那么，对于i与Max_right的位置关系，有两种情况
第一种情况:i<=Max_pos
这时，我们先找出i关于pos对称的位置j.因为Max_right和pos实际上记录的是一个长回文串，这个回文串内部是关于pos对称的，所以len[i]>=len[j]，而当len[j]延伸不到这个长回文串以外时(即len[j]<=Max_right-i)，len[i]=len[j]，否则就进行一个一个的匹配同时更新len[i]。此处输入图片的描述
第二种情况:i>Max_pos
这种情况意味着我们从未匹配过这一段，那么我们只能进行暴力匹配。
进行对于每个值的操作后都更新一下pos和Max_right值，就可以顺利的求出len数组了。
此处输入图片的描述
求出len数组后，略过那些加入的符号，直接求任何值都可以

  1. void Manacher(int length){
  2.     for (int i=1;i<=length;i++){
  3.         if (i<Max_right_pos){
  4.             len[i]=max(Max_right_pos-i,len[2*pos-i]);
  5.         };
  6.         else len[i]=1;
  7.         while (buf[i+len[i]]==buf[i-len[i]]) len[i]++;
  8.         if (len[i]+i>Max_right_pos){
  9.             pos=i;
  10.             Max_right_pos=len[i]+i;
  11.         }
  12.     }
  13. }

查找

一提到查找，就知道我要介绍一种数据结构。
的确，对于在各个部分中的查找操作，自然是把它们组织到一些特定的组织形式中查找更为方便。
而在字符串中，由于字符中字符集状态有限的特点，将其组织为类似字典的形式则更为美好(糟糕的台词)
于是我就要开始说Trie树
Trie树
trie树又叫字典树，但是未必只包含字母，只要处理的字符是有限的且不是太多就可以。
trie树的思想实际就是将字符串拆成一个一个字符，每个字符对应一个节点，在节点上打上标记和相关信息.
此处输入图片的描述
可以看到，在trie树中，除根节点外的每一个节点存储的都为这有限字符集中的一个字符，同时连接向其他的字符。通常我们会在这些节点上储存信息，也就是说，打出trie树往往只是很多题的第一步。
在这里简单的讲解一下trie树的基本操作
建树
对于每一个节点，只需用一个结构体表示

  1. const int knum=27,maxn=1000,maxlen=50;
  2. struct node{
  3.     int next[knum];//连接向的节点的编号 
  4.     bool flag;//以当前节点结尾的字符串是否为一个单词 
  5.     void init(){
  6.         memset(next,0,sizeof(next));
  7.         flag=0;
  8.     }
  9. };
  10. node index[maxn*maxlen];
  11. int cnt=0;//表示树中节点数 
  12. void root_init(){//初始化
  13.     index[++cnt].init();
  14. }

插入
我们一开始这棵树是只有一个根节点的，每次插入单词的时候沿着单词的边走，节点为空则新建节点。

  1. void insert(char *buf){//buf是插入的单词
  2.     int len=strlen(buf);
  3.     int u=1;
  4.     for (int i=0;i<len;i++){
  5.         int num=buf[i]-'a';
  6.         if (index[u].next[num]===0){
  7.             index[++cnt].init();//节点为空则新建
  8.             index[u].next[num]=cnt;
  9.         }
  10.         u=index[u].next[num];//进入下一个节点
  11.     }
  12.     index[u].flag=1;//标记此为一个单词的结尾
  13. }

查找
查找的操作和插入是几乎一样的，同样是按照字符的状态按边找

  1. bool find(char *buf){
  2.     int len=strlen(buf);
  3.     int u=1;
  4.     for (int i=0;i<len;i++){
  5.         int num=buf[i]-'a';
  6.         if (index[u].next[num]==0) return 0;//如果这个节点不存在，也就是说从来没有单词到那，自然没有
  7.         u=index[u].next[num];//进入下一个节点
  8.     }
  9.     return index[u].flag;//找到这个节点并不意味着有这个单词，还需要查看flag
  10. }

其他的操作什么的都是因题而异的，甚至有的时候有限字符集都不一样，这时候一定要学会变通。

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注