博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
理解字符串循环同构的最小表示法
阅读量:4595 次
发布时间:2019-06-09

本文共 1223 字,大约阅读时间需要 4 分钟。

循环字符串的最小表示法的问题可以这样描述:

对于一个字符串S,求S的循环的同构字符串S’中字典序最小的一个。

由于语言能力有限,还是用实际例子来解释比较容易:

设S=bcad,且S’是S的循环同构的串。S’可以是bcad或者cadb,adbc,dbca。而且最小表示的S’是adbc。
对于字符串循环同构的最小表示法,其问题实质是求S串的一个位置,从这个位置开始循环输出S,得到的S’字典序最小。
一种朴素的方法是设计i,j两个指针。其中i指向最小表示的位置,j作为比较指针。

令i=0,j=1

如果S[i] > S[j] i=j, j=i+1
如果S[i] < S[j] j++
如果S[i]==S[j] 设指针k,分别从i和j位置向下比较,直到S[i] != S[j]
         如果S[i+k] > S[j+k] i=j,j=i+1
         否则j++
返回i

起初,我想在j指针后移的过程中加入一个优化。就是j每次不是加1,而是移动到l位置。其中,l>j且S[l]<=S[j]。但是,即使加入这一优化,在遇到bbb…bbbbbba这样的字符串时复杂度将退化到O(n^2)。

注意到,朴素算法的缺陷在于斜体的情况下i指针的移动太少了。针对这一问题改进就得到了最小表示法的算法。最小表示法的算法思路是维护两个指针i,j。

令i=0,j=1

如果S[i] > S[j] i=j, j=i+1
如果S[i] < S[j] j++
如果S[i]==S[j] 设指针k,分别从i和j位置向下比较,直到S[i] != S[j]
         如果S[i+k] > S[j+k] i=i+k
         否则j++
返回i和j的小者

注意到上面两个算法唯一的区别是粗体的一行。这一行就把复杂度降到O(n)了。

值得一提的是,与KMP类似,最小表示法处理的是一个字符串S的性质,而不是看论文时给人感觉的处理两个字符串。
应用最小表示法判断两个字符串同构,只要将两个串的最小表示求出来,然后从最小表示开始比较。剩下的工作就不用多说了。

[cpp:nogutter] 
  1. int MinimumRepresentation(char *s, int l)  
  2. {  
  3.     int i = 0, j = 1, k = 0, t;  
  4.     while(i < l && j < l && k < l) {  
  5.         t = s[(i + k) >= l ? i + k - l : i + k] - s[(j + k) >= l ? j + k - l : j + k];  
  6.         if(!t) k++;  
  7.         else{  
  8.             if(t > 0) i = i + k + 1;  
  9.             else j = j + k + 1;  
  10.             if(i == j) ++ j;  
  11.             k = 0;  
  12.         }  
  13.     }  
  14.     return (i < j ? i : j);  
  15. }  

转载于:https://www.cnblogs.com/catkins/archive/2012/09/05/5270774.html

你可能感兴趣的文章
JQuery和Js中,如何让ajax执行完后再继续往下执行?(已解决,示例)
查看>>
VMWare12pro安装Centos 6.9教程
查看>>
Spark笔记之使用UDF(User Define Function)
查看>>
找规律 UVALive 6506 Padovan Sequence
查看>>
区间DP UVA 10453 Make Palindrome
查看>>
JavaScript系列教程(七):函数
查看>>
江中微型统计分析软件V1.0版本完成
查看>>
彻底搞懂CNN中的卷积和反卷积
查看>>
iOS中画各种图形
查看>>
javascript中的面向对象
查看>>
VirtualBox 下 CentOS6.5 网络配置(NAT) (公司内部用)
查看>>
XGBOOST/GBDT,RandomForest/Bagging的比较
查看>>
python迭代器
查看>>
世界大部分的变化变革是一直有人在问为什么不能做得更好。
查看>>
关于wav文件fft处理后x,y轴坐标数据的问题
查看>>
HDU 2546 0-1背包问题
查看>>
mysql show processlist 显示mysql查询进程
查看>>
centos系统安装后的基本配置
查看>>
遍历集合的Iterator删除其中的元素
查看>>
Linux
查看>>