现在的位置: 首页 > 综合 > 正文

字符串相关处理kmp，前缀数，后缀树，后缀数组，最长回文串，最长重复字串，最长非重复字串 字符串相关处理kmp，前缀数，后缀树，后缀数组，最长回文串，最长重复字串，最长非重复字串

2017年12月17日 ⁄ 综合 ⁄ 共 8807字 ⁄ 字号 小 中 大 ⁄ 评论关闭

字符串相关处理kmp，前缀数，后缀树，后缀数组，最长回文串，最长重复字串，最长非重复字串

分类： 算法2012-05-13
11:44 935人阅读 评论(0) 收藏 举报
算法zkc优化

1. 最长回文串

一般用后缀数组或者后缀树可以解决，

用此方法：http://blog.csdn.net/v_july_v/article/details/6897097

  1. 预处理后缀树，使得查询LCA的复杂度为O(1)。这步的开销是O(N)，N是单词S的长度 ；
  2. 对单词的每一位置i(也就是从0到N-1)，获取LCA(S(i), S‘(N-i-1)) 以及LCA(S(i), S’(n-i))。查找两次的原因是我们需要考虑奇数回文和偶数回文的情况。这步要考察每坨i，所以复杂度是O(N) ；（s'是s的翻转串）
  3. 找到最大的LCA，我们也就得到了回文的中心i以及回文的半径长度，自然也就得到了最长回文。总的复杂度O(n)。 （在前文中提到求树种两个节点的最近公共父节点也是用的lca，此题也是相类似，找到s和s'的最近父节点之后可以，则父节点到root之间的便是回文）
（上面讲得太复杂，
对于串S，取其反转S'
将S和S‘插入后缀树中
for i [1 to n - 1]
   找出S[0 - i].reverse() 与 S[i, n]的LCA
   找出S[0 - i].reverse() 与 S[i + 1, n]的LCA
从些个LCAs里面选出最大的1

）

1.1 是不是想到一种求s和s'最长公共子串（注意不是最长公共子序列）？

     这个方法在有时候不work，

S = “abacdfgdcaba”, S’ = “abacdgfdcaba”.
The longest common substring between S and S’ is “abacd”.明显错误。

1.2

依次遍历字符串S中可能的中心点，注意，中心点可能在字符，也可能在两个字符之间

[cpp] view
plaincopy

  1. //从中心向两端扩展  
  2.  string expandAroundCenter(string s,int c1,int c2)  
  3.  {  
  4.      int l=c1;  
  5.      int r=c2;  
  6.      int n=s.length();  
  7.      while (l>=0 && r<=n-1 && s[l]==s[r])  
  8.      {  
  9.          l--;  
  10.          r++;  
  11.      }  
  12.      return s.substr(l+1,r-l-1);  
  13.  }  
  14.    
  15.  //方法3：从中心向两端扩展  
  16.  string IsPalindrome3(string str)  
  17.  {  
  18.      int n=str.length();  
  19.      if (n==0)  
  20.      {  
  21.          return "";  
  22.      }  
  23.      string longest=str.substr(0,1);  
  24.      for (int i=0;i<n-1;i++)  
  25.      {  
  26.          string p1=expandAroundCenter(str,i,i);  
  27.          if (p1.length()>longest.length())  
  28.          {  
  29.              longest=p1;  
  30.          }  
  31.          string p2=expandAroundCenter(str,i,i+1);  
  32.          if (p2.length()>longest.length())  
  33.          {  
  34.              longest=p2;  
  35.          }  
  36.      }  
  37.      return longest;  
  38.  }  

1.3 动态规划（时间复杂度也是n^2）

Define P[ i, j ] ← true iff the
substring Si … Sj is
a palindrome, otherwise false.

P[ i, j ] ← ( P[ i+1, j-1 ] and Si =
Sj )

This yields a straight forward DP solution, which we first initialize
the one and two letters palindromes, and work our way up finding all three letters palindromes, and so on… 

[cpp] view
plaincopy

  1. //方法2：动态规划  
  2.  string IsPalindrome2(string str)  
  3.  {  
  4.      if (str=="")  
  5.      {  
  6.          return "";  
  7.      }  
  8.      int n=str.length();  
  9.      int maxIndex=0;  
  10.      int maxLength=1;  
  11.      bool IsPal[1000][1000]={false};  
  12.       
  13.      for (int i=0;i<n;i++)  
  14.      {  
  15.          IsPal[i][i]=true;  
  16.      }  
  17.      for (int i=0;i<n-1;i++)  
  18.      {  
  19.          if (str[i]==str[i+1])  
  20.          {  
  21.              IsPal[i][i+1]=true;  
  22.              maxIndex=i;  
  23.              maxLength=2;  
  24.          }  
  25.      }  
  26.      for (int len=3;len<=n;len++)  
  27.      {  
  28.          for (int i=0;i<=n-len;i++)  
  29.          {  
  30.              int j=i+len-1;  
  31.              if (IsPal[i+1][j-1] && str[i]==str[j])  
  32.              {  
  33.                  IsPal[i][j]=true;  
  34.                  maxIndex=i;  
  35.                  maxLength=len;  
  36.              }  
  37.          }  
  38.      }  
  39.       
  40.      return str.substr(maxIndex,maxLength);  
  41.  }  

1.4

但是有一种巧妙的方法，不构建后缀树在o(n)完成

转自:http://www.felix021.com/blog/read.php?2040

首先用一个非常巧妙的方式，将所有可能的奇数/偶数长度的回文子串都转换成了奇数长度：在每个字符的两边都插入一个特殊的符号。比如 abba 变成 #a#b#b#a#， aba变成 #a#b#a#。 为了进一步减少编码的复杂度，可以在字符串的开始加入另一个特殊字符，这样就不用特殊处理越界问题，比如$#a#b#a#。

下面以字符串12212321为例，经过上一步，变成了 S[] = "$#1#2#2#1#2#3#2#1#";

然后用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度（包括S[i]），比如S和P的对应关系：

S  #  1  #  2  #  2  #  1  #  2  #  3  #  2  #  1  #
P  1  2  1  2  5  2  1  4  1  2  1  6  1  2  1  2  1
(p.s. 可以看出，P[i]-1正好是原字符串中回文串的总长度）

那么怎么计算P[i]呢？该算法增加两个辅助变量（其实一个就够了，两个更清晰）id和mx，其中id表示最大回文子串中心的位置，mx则为id+P[id]，也就是最大回文子串的边界。

然后可以得到一个非常神奇的结论，这个算法的关键点就在这里了：如果mx > i，那么P[i] >= MIN(P[2 * id - i], mx - i)。就是这个串卡了我非常久。实际上如果把它写得复杂一点，理解起来会简单很多：

//记j = 2 * id - i，也就是说 j 是 i 关于 id 的对称点。
if (mx - i > P[j]) 
    P[i] = P[j];
else /* P[j] >= mx - i */
    P[i] = mx - i; // P[i] >= mx - i，取最小值，之后再匹配更新。

当然光看代码还是不够清晰，还是借助图来理解比较容易。

当 mx - i > P[j] 的时候，以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中，由于 i 和 j 对称，以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中，所以必有 P[i] = P[j]，见下图。
点击在新窗口中浏览此图片

当 P[j] > mx - i 的时候，以S[j]为中心的回文子串不完全包含于以S[id]为中心的回文子串中，但是基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以S[i]为中心的回文子串，其向右至少会扩张到mx的位置，也就是说 P[i] >= mx - i。至于mx之后的部分是否对称，就只能老老实实去匹配了。
点击在新窗口中浏览此图片

对于 mx <= i 的情况，无法对 P[i]做更多的假设，只能P[i] = 1，然后再去匹配了。

于是代码如下：

//输入，并处理得到字符串s
int p[1000], mx = 0, id = 0;
memset(p, 0, sizeof(p));
for (i = 1; s[i] != '\0'; i++) {
    p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
    while (s[i + p[i]] == s[i - p[i]]) p[i]++;
    if (i + p[i] > mx) {
        mx = i + p[i];
        id = i;
    }
}
//找出p[i]中最大的
//主要原理就是先通过对称性获得以i为中心点的半径；然后再向左向右扩展，试图增大半径
[cpp] view
plaincopy

  1. int Palindrome(char *str)  
  2. {  
  3.     int len = strlen(str);  
  4.   
  5.     char *Str = new char[len+len+3];  
  6.       
  7.     memset(Str,0,len+len+3);//  
  8.     Str[0] = '$';  
  9.     int Len = len+len+2;  
  10.     int *scale = new int[Len];  
  11.     memset(scale,0,sizeof(int)*Len);  
  12.     int j=0;  
  13.     for (int i=1;i<Len;++i)  
  14.     {  
  15.         if(i%2==0)  
  16.             Str[i] = str[j++];  
  17.         else  
  18.             Str[i] = '#';  
  19.     }  
  20.     Str[Len] = '\0';  
  21.       
  22.     int id = 0;//在i之前的回文段，这个回文段的中心点，这个回文段的右边的边界最大  
  23.     int mx  = 0;//在i之前的回文段，这个回文段的右边的边界最大  
  24.       
  25.     for (int i=1;i<Len;++i)  
  26.     {  
  27.           
  28.         if (mx >i)//如果之前的回文边界超过i,要找到i关于回文中心点id的对称点j  
  29.         {  
  30.             int j = 2*id - i;  
  31.             int rightSpan = mx - i;  
  32.             if(scale[j]>rightSpan)  
  33.                 scale[i] = rightSpan;  
  34.             else  
  35.                 scale[i] = scale[j];  
  36.         }else scale[i] = 1;  
  37.         int right = i + scale[i] +1;  
  38.         int left = i - scale[i] -1;  
  39.         while ( (right<Len) && (Str[right]==Str[left]) )  
  40.         {  
  41.             ++scale[i];  
  42.             ++right;  
  43.             --left;  
  44.         }  
  45.   
  46.         if (i+scale[i]>mx)  
  47.         {  
  48.             mx = scale[i];  
  49.             id = i;  
  50.         }  
  51.           
  52.     }  
  53.   
  54.     int maxValue = 0;  
  55.     //cout<<"Len "<<Len<<endl;  
  56.     for (int i=0;i<Len;++i)  
  57.     {  
  58.         //cout<<i<<endl;  
  59.         if(scale[i]>maxValue)  
  60.             maxValue = scale[i];  
  61.     }  
  62.     //cout<<"out"<<endl;  
  63.     delete []Str;  
  64.     delete []scale;  
  65.     return maxValue ;  
  66.   
  67. }  
2. july：http://blog.csdn.net/v_july_v/article/details/6897097提到后缀树还可以解决一下几个问题：
  1. 查找字符串o是否在字符串S中。 
      方案：用S构造后缀树，按在trie中搜索字串的方法搜索o即可。 
      原理：若o在S中，则o必然是S的某个后缀的前缀。 
    例如S: leconte，查找o: con是否在S中,则o(con)必然是S(leconte)的后缀之一conte的前缀.有了这个前提，采用trie搜索的方法就不难理解了。。 
  2. 指定字符串T在字符串S中的重复次数。 
      方案：用S+’$'构造后缀树，搜索T节点下的叶节点数目即为重复次数 
      原理：如果T在S中重复了两次，则S应有两个后缀以T为前缀，重复次数就自然统计出来了。。 
  3. 字符串S中的最长重复子串 
      方案：原理同2，具体做法就是找到最深的非叶节点。 
      这个深是指从root所经历过的字符个数，最深非叶节点所经历的字符串起来就是最长重复子串。 
    为什么要非叶节点呢?因为既然是要重复，当然叶节点个数要>=2。 （此方法应该只能找到可重叠的最长重复字串，譬如abcbcbd,可重叠最长重复字串是bcb,可以看出两个字串bcb在b上重叠了；其不重叠最长重复字串是bc和cb，用后缀树暂时想不出什么方法）
  4. 两个字符串S1，S2的最长公共部分 
      方案：将S1#S2$作为字符串压入后缀树，找到最深的非叶节点，且该节点的叶节点(这里是指该节点的所有叶子节点)既有#也有$。 （    譬如s1=abcd, s2 = ebce,连接组合成abcd#ebce$,     

 

也可以将abcd#,ebce$分布放入后缀树中，找到深度最大，并且属于所有字符串的前缀，如：http://nanapple.happy.blog.163.com/blog/static/77501222200861583550778/

}

第四题可以看做是longest common substring,可以就是说要求最长公共字串必须是连续的，用后缀树或者后缀数组的时间复杂度是o(n+m)

当然还可以用动态规划实现,o(n*m)：（为了避免边界检查，f[][]都是从1开始计算的，但是f[i][j],表示的是a[i-1]b[j-1]）

[cpp] view
plaincopy

  1. char a[]="acbedf";  
  2.     char b[]="ecbedfacabe";  
  3.     int f[50][50];  
  4.     memset(f,0,sizeof(f));  
  5.     int maxL=0,ai=0;  
  6.   
  7.     for (int i=1;i<=sizeof(a);++i)  
  8.     {  
  9.         for(int j=1;j<=sizeof(b);++j)  
  10.         {  
  11.             if(a[i-1]==b[j-1])  
  12.             {  
  13.                 f[i][j] =f[i-1][j-1] +1;  
  14.                 if (f[i][j]>maxL)  
  15.                 {  
  16.                     maxL = f[i][j];  
  17.                     ai = i-1;  
  18.                 }  
  19.                   
  20.             }  
  21.         }  
  22.     }  
  23.     char c[50];  
  24.     memset(c,0,sizeof(c));  
  25.     strncpy(c,a+ai-maxL+1,maxL);  
  26.     cout<<maxL<<endl<<c<<endl;  

以上代码主要参考：http://sagittarix.blogspot.com/2008/11/blog-post_06.html

\

e

d

c

e

d

n

n

0

0

0

0

0

1

c

0

0

1

0

0

0

e

1

0

0

1

0

0

d

0

1

0

0

1

0

t

0

0

0

0

0

0

我们把两个字符串看作矩阵的x-y轴：首先遍历字符串时，把两个字符相同的位置标记成1，不相同的地方标记成0。很容易证明，如果能形成公共子序列，则最长子序列一定是从某个位置开始的对角线的长度，所以我们需要做的就是统计对角线的长度。

例如str1=”ncedt”与str2=”edcedn”生成的矩阵如左矩阵，遍历找到最长的对角线即可。

e

d

c

e

d

n

n

0

0

0

0

0

1

c

0

0

1

0

0

0

e

1

0

0

2

0

0

d

0

2

0

0

3

0

t

0

0

0

0

0

0

其实这里还可以优化，即在生成表格的时候，加上对角线上比它前面的元素，这样一遍遍历就可以生成左图所示矩阵，中间记下最大值便可，省下最后一趟比较，降低时间复杂度；空间复杂度也可降低，其实只要一维的数组便可以了，因为每次更新只用到上面一行(或左边一列，看你程序怎么写了，都可以)。

这个直观上很好理解，但拆分到子问题的思想表达起来比较绕，就转一下别人的文字：

---------------------------------------------------------------------------------------------------------------------

定义f(m, n)为串Xm和Yn之间最长的子字符串的长度并且该子字符串结束于Xm 和 Yn。因为要求是连续的，所以定义f的时候多了一个要求，即字符串结束于Xm 和 Yn。

于是有f(m, 0) = f(0, m) = 0
如果xm != yn, 则f(m, n) = 0
如果xm = yn, 则f(m, n) = f(m-1, n-1) + 1
因为最长字符串不一定结束于Xm 和 Yn末尾，所以这里必须求得所有可能的f(p, q) | 0 <>最大的f(p, q)就是解。依照公式用Bottom-up DP可解。

代码就不写了，简单。但是它与其它的DP填表又有所不同，不是直接得出最大的填到表格最后一格中，而是找出格子中的最大值，其中差别，细细体会

还有一个问题是 longest common subsquence ，要求最长公共序列不一定是连续的，但是有序的，一般只能用动态规划实现，o(n*m)

算法导论讲的很透彻，这个博客也不错：http://blog.csdn.net/orbit/article/details/6717125

 现在来分析一下本问题的最优子结构。首先定义问题，假设有字符串str1长度为m，字符串str2长度为n，可以把子问题描述为：求字符串str1<1..m>中从第1个到第i（i <= m）个字符组成的子串str1<1…i>和字符串str2<1..n>中从第1个到第j(j <= n)个字符组成的子串str2<1…j>的最长公共序列，子问题的最长公共序列可以描述为d[i,j] = { Z1,Z2, … Zk }，其中Z1-Zk为当前子问题已经匹配到的最长公共子序列的字符。子问题定义以后，还要找出子问题的最优序列d[i,j]的递推关系。分析d[i,j]的递推关系要从str1[i]和str2[j]的关系入手，如果str1[i]和str2[j]相同，则d[i,j]就是d[i-1,j-1]的最长公共序列＋1，Zk=str1[i]=str2[j]；如果str1[i]和str2[j]不相同，则d[i,j]就是d[i-1,j]的最长公共序列和d[i,j-1]的最长公共序列中较大的那一个。

        最后是确定d[i,j]的边界值，当字符串str1为空或字符串str2为空时，其最长公共子串应该是0，也就是说当i=0或j=0时，d[i,j]就是0。d[i,j]的完整递推关系如下：

d[i,j]表示，对于序列str1[0,i]和str2[0,j]的lcs

构建一颗后缀树的编码难度较大，一般解题应该用后缀数组：http://dongxicheng.org/structure/suffix-array/

有时间再研究下后缀数组吧。。。

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞