- 浏览: 1404089 次
- 性别:
- 来自: 广州
-
文章分类
最新评论
-
sdgxxtc:
[quo[color=red]te][/color]
C#使用OleDb读取Excel,生成SQL语句 -
zcs302567601:
博主,你好,一直都有个问题没有搞明白,就是 2.x的版本是通过 ...
NGUI所见即所得之UIPanel -
一样的追寻:
感谢楼主!
有向强连通和网络流大讲堂——史无前例求解最大流(最小割)、最小费用最大流 -
cp1993518:
感谢!从你的博客里学到了很多
Unity日志工具——封装,跳转 -
cp1993518:
学习了~,话说现在的版本custom还真的变委托了
NGUI所见即所得之UIGrid & UITable
最长重复子串和最长不重复子串求解
本文内容框架:
§1 最长重复子串
基本方法、KMP算法求解、后缀数组求解
§2 最长不重复子串
基本方法、动态规划、动态规划+Hash
§3 小结
§1最长重复子串
1.1问题描述
首先这是一个单字符串问题。子字符串R 在字符串L 中至少出现两次,则称R 是L 的重复子串。重复子串又分为可重叠重复子串和不可重叠重复子串。
1.2基本方法
枚举子串,让子串和子串进行比较。直接看代码:
╔
/* 最长重复子串 Longest Repeat Substring */ int maxlen; /* 记录最长重复子串长度 */ int maxindex; /* 记录最长重复子串的起始位置 */ void outputLRS(char * arr); /* 输出LRS */ /* 最长重复子串 基本算法 */ int comlen(char * p, char * q) { int len = 0; while(*p && *q && *p++ == *q++) { ++len; } return len; } void LRS_base(char * arr, int size) { for(int i = 0; i < size; ++i) { for(int j = i+1; j < size; ++j) { int len = comlen(&arr[i],&arr[j]); if(len > maxlen) { maxlen = len; maxindex = i; } } } outputLRS(arr); }
╝①
优化思路
一般的优化方法就是在充分利用已有的结果,最长重复子串的长度增加一定是建立在之前已经找到的重复子串之上的,充分利用已找到的重复子串的位置和长度是优化的一个重点,此外还有就是未不是重复子串的,以后就不会被包含在重复子串内,如"ab"只有一个,则重复子串就不能包含"ab"(允许重叠的重复子串例外)。
1.2KMP算法求解
对KMP算法还不是很了解的,可以查看我的另一篇博文(不懂猛点),在KMP算法的关键就是求解next数组,针对next[j]=k,可以得到P[0,1,...,k-1]=P[j-k,j-k+1,...,j-1]。看到P[0,1,...,k-1]=P[j-k,j-k+1,...,j-1]应该会眼前一亮,大脑顿时清醒些,这不就是重复子串吗!由此求解最长重复子串就转化为求解KMP算法next数组中的最大值(即max{next[j]=k}。
现在就是求解next数组的问题了,还是直接查看代码:
╔
int getNext(char *str,int *next) { int len=strlen(str); int index=0; int k=-1; next[0]=k; int max=0; //kmp算法求next值,取得最大的字串 while (index<len) { if (k==-1 || str[index]==str[k]) { k++; index++; next[index]=k; if (k>max)//求得其中重复最大的字串的个数,也就是与最前面串的重复数 { max=k; } } else k=next[k]; } return max; } int main() { char str[50];//输入字符串 cin>>str; int max=0;//最大的字串 int nextMax;//接受getNext函数中返回的最大值 int index; int maxIndex;//保存最大的字串起始位置 int len=strlen(str); //将一个字符串从开始一直减少到只剩一个字符,通过这个取得最小字串 for (index=0;index<len-1;index++) { int *next=new int[len-index];//取得next在这没用 nextMax=getNext(str+index,next);//每次从str+index开始 if (nextMax>max) { max=nextMax; maxIndex=index; } } //输出最长字串 cout<<"最长字串: "; for (index=0;index<max;index++) { cout<<str[index+maxIndex]; } cout<<endl; return 0; }
╝②
1.3后缀数组求解
后缀数组在我的另外一篇博文有介绍,还没有概念的可以移步查看点击。后缀数组就是保留字符串所有位置到字符串末尾的子字符串,a[i]就是第i位置到末尾的子串。有了后缀数组,对后缀数组进行排序,然后进行求后缀数组相邻元素的最大前缀就是最大重复子串。
╔
#include <iostream> using namespace std; const int MAXN = 1000; int mycmp(const void* p1, const void* p2) { return strcmp(*(char* const*)p1, *(char* const*)p2); } int getLen(char* p, char* q) { int ret = 0; while (*p && *p++ == *q++) { ++ret; } return ret; } char* foo(char result[], char s[]) { int len = strlen(s); char** suffix = new char*[len]; for (int i = 0; i < len; ++i) { suffix[i] = s + i; } qsort(suffix, len, sizeof (char*), mycmp); //for (int i = 0; i < len; ++i) //{ // cout << suffix[i] << endl; //} int maxlen = 0, maxi = 0, maxj = 0, temp = 0; for (int i = 0; i < len - 1; ++i) { temp = getLen(suffix[i], suffix[i + 1]); if (temp > maxlen) { maxlen = temp; maxi = i; maxj = i + 1; } } //cout << maxlen << endl; //cout << suffix[maxi] << endl; //cout << suffix[maxj] << endl; //printf("%.*s\n", maxlen, suffix[maxi]); for (int i = 0; i < maxlen; ++i) { result[i] = suffix[maxi][i]; } result[maxlen] = '\0'; return result; } int main() { char s[MAXN]; char result[MAXN]; while (cin >> s) { cout << foo(result, s) << endl; } return 0; }
╝③
§2最长不重复子串
╔
2.1问题描述
从一个字符串中找到一个连续子串,该子串中任何两个字符不能相同,求子串的最大长度并输出一条最长不重复子串。
下面介绍四种方法逐步优化,时间复杂度从O(n²)到O(n)。
2.2基本算法(使用hash)
要求子串中的字符不能重复,判重问题首先想到的就是hash,寻找满足要求的子串,最直接的方法就是遍历每个字符起始的子串,辅助hash,寻求最长的不重复子串,由于要遍历每个子串故复杂度为O(n^2),n为字符串的长度,辅助的空间为常数hash[256]。
/* 最长不重复子串 设串不超过30 * 我们记为 LNRS */ int maxlen; int maxindex; void output(char * arr); /* LNRS 基本算法 hash */ char visit[256]; void LNRS_hash(char * arr, int size) { int i, j; for(i = 0; i < size; ++i) { memset(visit,0,sizeof visit); visit[arr[i]] = 1; for(j = i+1; j < size; ++j) { if(visit[arr[j]] == 0) { visit[arr[j]] = 1; }else { if(j-i > maxlen) { maxlen = j - i; maxindex = i; } break; } } if((j == size) && (j-i > maxlen)) { maxlen = j - i; maxindex = i; } } output(arr); }
2.3动态规划求解
动态规划思想就是用于处理有重叠问题的求解,最大不重复子串一定是两个相同字符夹着的一段字符串加上这个字符,如abcac这里的最大不重复子串是a夹的一段。
当一个最长子串结束时(即遇到重复的字符),新的子串的长度是与第一个重复的字符的下标有关的,如果该下标在上一个最长子串起始位置之前,则dp[i] = dp[i-1] + 1,即上一个最长子串的起始位置也是当前最长子串的起始位置;如果该下标在上一个最长子串起始位置之后,则新的子串是从该下标之后开始的。简短几句话可能讲不是很明白,不过好在有程序可以帮助理解,惯例下面附上程序:
/* LNRS dp */ int dp[30]; void LNRS_dp(char * arr, int size) { int i, j; int last_start = 0; // 上一次最长子串的起始位置 maxlen = maxindex = 0; dp[0] = 1; for(i = 1; i < size; ++i) { for(j = i-1; j >= last_start; --j) // 遍历到上一次最长子串起始位置 { if(arr[j] == arr[i]) { dp[i] = i - j; last_start = j+1; // 更新last_start break; }else if(j == last_start) // 无重复 { dp[i] = dp[i-1] + 1; } } if(dp[i] > maxlen) { maxlen = dp[i]; maxindex = i + 1 - maxlen; } } output(arr); }
2.4动态规划+Hash求解
上面动态规划求解时间复杂度还是O(n²),主要是还是进行“回头”查找了重复元素位置,其实,上面并不是真正的动态规划方法,因为上面的求解过程没有记录有用的结果,所以可以通过记录之前出现的下标来改进算法,这样就不用每次都回去查找重复元素位置,这其实才是真正的动态规划方法,只是记录结果是用的Hash,这样的时间复杂度就是O(n)。
/* LNRS dp + hash 记录下标 */ void LNRS_dp_hash(char * arr, int size) { memset(visit, -1, sizeof visit); memset(dp, 0, sizeof dp); maxlen = maxindex = 0; dp[0] = 1; visit[arr[0]] = 0; int last_start = 0; for(int i = 1; i < size; ++i) { if(visit[arr[i]] == -1) { dp[i] = dp[i-1] + 1; visit[arr[i]] = i; /* 记录字符下标 */ }else { if(last_start <= visit[arr[i]]) { dp[i] = i - visit[arr[i]]; last_start = visit[arr[i]] + 1; visit[arr[i]] = i; /* 更新最近重复位置 */ }else { dp[i] = dp[i-1] + 1; } } if(dp[i] > maxlen) { maxlen = dp[i]; maxindex = i + 1 - maxlen; } } output(arr); }
进一步优化
上面的程序因为辅助的空间多了,是不是还能优化,仔细看DP最优子问题解的更新方程:
dp[i] = dp[i-1] + 1;
dp[i-1]不就是更新dp[i]当前的最优解么?这与最大子数组和问题的优化几乎同出一辙,我们不需要O(n)的辅助空间去存储子问题的最优解,而只需O(1)的空间就可以了,至此,我们找到了时间复杂度O(N),辅助空间为O(1)(一个额外变量与256大小的散列表)的算法,代码如下:
注意:当前最长子串的构成是与上一次最长子串相关的,故要记录上一次最长子串的起始位置!
/* LNRS dp + hash 优化 */ void LNRS_dp_hash_impro(char * arr, int size) { memset(visit, -1, sizeof visit); maxlen = maxindex = 0; visit[arr[0]] = 0; int curlen = 1; int last_start = 0; for(int i = 1; i < size; ++i) { if(visit[arr[i]] == -1) { ++curlen; visit[arr[i]] = i; /* 记录字符下标 */ }else { if(last_start <= visit[arr[i]]) { curlen = i - visit[arr[i]]; last_start = visit[arr[i]] + 1; visit[arr[i]] = i; /* 更新最近重复位置 */ }else { ++curlen; } } if(curlen > maxlen) { maxlen = curlen; maxindex = i + 1 - maxlen; } } output(arr); }
最后在给出测试用例
/* 输出LNRS */ void output(char * arr) { if(maxlen == 0) { printf("NO LNRS\n"); } printf("The len of LNRS is %d\n",maxlen); int i = maxindex; while(maxlen--) { printf("%c",arr[i++]); } printf("\n"); } void main() { char arr[] = "abcaacdeabacdefg"; /* LNRS 基本算法 */ LNRS_hash(arr,strlen(arr)); /* LNRS dp */ LNRS_dp(arr,strlen(arr)); /* LNRS dp + hash 记录下标 */ LNRS_dp_hash(arr,strlen(arr)); /* LNRS dp + hash 优化方案 */ LNRS_dp_hash_impro(arr,strlen(arr)); }
╝④
§3 小结
这篇文章把字符串最长重复子串和最长不重复子串的求解方法,能有了一定的认识和理解,基本可以掌握这些方法。如果你有任何建议或者批评和补充,请留言指出,不胜感激,更多参考请移步互联网。
参考:
①勇幸|Thinking: http://www.ahathinking.com/archives/121.html
②huang12315: http://blog.csdn.net/huang12315/article/details/6455090
③unixfy: http://www.cppblog.com/unixfy/archive/2011/05/23/146986.html
④勇幸|Thinking: http://www.ahathinking.com/archives/123.html
评论
发表评论
-
C#使用OleDb读取Excel,生成SQL语句
2013-06-27 15:47 10042C#使用OleDb读取Excel,生成SQL语句 ... -
C#读写XML文件工具类——满足一切需求
2013-06-18 07:33 10753C#读写XML文件工具类— ... -
C#解析XML
2013-06-17 19:20 0覆盖 -
C#读取Excel数据动态生成对象并进行序列化
2013-06-16 20:10 7949C#读取Excel数据 ... -
Unity导入unitypackage总是失败问题原因
2013-06-11 22:54 11453最近尝试手游开发,用的Unity引擎,然后开 ... -
C# socket连接服务器发送和接收数据在设置断点单步执行没有问题但是直接运行不能成功
2013-06-04 20:26 5937题目有点长, ... -
C# 调用Delegate.CreateDelegate方法出现“未处理ArgumentException”错误解决
2013-05-31 12:24 3526在C# 调用Delegate.Create ... -
考题小记(希望能持续增加)
2013-04-03 16:11 0在一块黑板上将123456789重复50次得到450位数12 ... -
数组问题集结号
2012-12-06 22:01 0数组是最简单的数据结构,数组问题作为公司招聘的笔试和面试题目 ... -
算法问题分析笔记
2012-12-05 11:59 01.Crash Balloon Zhejiang Univer ... -
Java基础进阶整理
2012-11-26 09:59 2299Java学习笔记整理 ... -
Java学习笔记整理
2012-11-24 23:43 211Java学习笔记整理 本文档是我个人 ... -
《C++必知必会》学习笔记
2012-11-24 23:40 2609《C++必知必会》学 ... -
《C++必知必会》学习笔记
2012-11-24 23:34 1《C++必知必会》学习笔 ... -
Java文件输出时,文件大小只有24KB
2012-11-14 22:10 1591今天,用Java做点事情,出现了一个很莫名其妙的事情就是文件 ... -
C语言名题精选百则——游戏问题
2012-11-05 23:27 86第8章游戏问题 问题8.1苞数阶魔方阵(MAGIC_O ... -
C语言名题精选百则——序曲
2012-11-04 23:27 2352C语言名题精选百则——序曲 ... -
C语言名题精选百则——数字问题
2012-11-04 23:25 4038C语言名题精选百则——数字问题 尊重他人的劳动, ... -
C语言名题精选百则——排序
2012-11-04 23:29 128第5章排 序 问题5.1 二分插入法(BIN ... -
C语言名题精选百则——查找
2012-11-04 23:29 4081尊重他人的劳动,支持原创 本篇博文,D.S.Q ...
相关推荐
在Python编程语言中,求解两个字符串的最长公共子串是一项常见的字符串处理任务。这个问题的解决方案通常基于动态规划思想,即将问题分解为更小的子问题,并存储子问题的解以便于后续使用,从而避免重复计算。下面...
Manacher's 算法是一种高效解决字符串中最长回文子串问题的算法,它能在O(n)的时间复杂度内完成,其中n是字符串的长度...在LeetCode等在线编程平台上,该算法常用于解决字符串处理问题,特别是求解最长回文子串的问题。
动态规划的基本思想是将一个复杂的问题分解成若干个更小的子问题,然后通过存储和重用子问题的解来避免重复计算,从而提高效率。 对于最长回文子串的动态规划算法,我们可以定义一个二维数组`matrix`,其中`matrix...
这个压缩包文件“python-leetcode面试题解之无重复字符的最长子串.zip”显然是一个关于解决LeetCode上特定问题的资源集合,问题的核心是寻找字符串中的最长无重复字符子串。 题目描述: 给定一个字符串`s`,找到...
Manacher's Algorithm的创新之处在于利用了回文串的对称性质来减少重复计算,通过维护一个回文半径中心P和回文右边界R,动态更新回文串的信息。当查找新位置i时,如果i在已知回文串的范围内,我们可以利用已知信息...
最长公共子串的求解同样基于动态规划,但因为子串要求连续性,数组`c[i][j]`的含义有所不同,它记录的是以`str1[i-1]`和`str2[j-1]`结尾的最长公共子串的长度。状态转移方程变为: 最长公共子串的长度是所有`c[i][j...
而LCS则不同,它不要求连续性,所以 "AE" 也是 "ABCDEF" 和 "ABEFGH" 的一个最长公共子序列,尽管它不是公共子串。 接下来,我们将从算法的角度探讨如何求解LCS。一种常见的方法是使用动态规划,这在计算机科学中是...
寻找字符串中最长的不包含重复字符的子串,例如,字符串"abcabcbb"的最长不重复子串是"abc"。 **最长回文子串** 最长回文子串是指字符串中最长的回文序列,即正读反读都一样的子串。例如,"babad"的最长回文子串有...
综上所述,Manacher算法作为一种专门针对回文子串求解的高效算法,通过巧妙的预处理和动态规划策略,将原本O(N^2)的复杂度降低至O(n),极大地提升了算法的性能。对于处理大规模数据集或需要快速响应的应用场景来说,...
本篇将深入探讨动态规划的两个实例:求解最长公共子串问题和取数游戏。 首先,我们来看第一个问题——求解两个小写字母组成的字符串的最长公共子串的长度。这个问题的核心在于定义状态和构建转移方程。我们可以用一...
Manacher算法是一种用于求解字符串中最长...总结来说,Manacher算法通过利用回文串的对称性,避免了重复计算,从而实现了线性时间复杂度的求解最长回文子串问题。这对于处理大规模数据非常有效,极大地提高了算法效率。
针对求解两个字符串的最长公共子串问题,如Spoj的LCS题目,我们可以采用以下策略: 1. **构造母串的后缀自动机**:首先,以其中一个字符串(母串A)为基础,构建后缀自动机。 2. **逐位扫描匹配串**:随后,逐字符...
本文将深入探讨四个与算法相关的知识点:单词矩阵中无重复字符的最长子串、处理不确定长度数组的输入、数独字符串求解以及识别三种括号的区别,以及最长公共子串问题。 首先,让我们讨论“单词矩阵无重复字符的最长...
=yj`且`i`和`j`均不为0,则`C[i,j]=max(C[i-1][j],C[i][j-1])`,表示当前字符不匹配,取两者之前的最大值作为当前的最长公共子串长度。 通过上述状态转移方程,最终可以在`C`矩阵中找到最长公共子串的长度及具体...
最长公共子序列问题与最长公共子串类似,不同的是,子序列不要求连续,而子串要求连续。动态规划同样适用于这个问题的解决。 17. 最长递增子序列(LIS) 最长递增子序列问题是在一个数组中找到最长的严格递增的子...
5. **动态规划思想**:虽然这个问题不是标准的动态规划问题,但它具有动态规划的性质,即通过维护当前窗口的状态(长度和是否存在重复字符)来逐步求解全局最优解。 6. **优化策略**:在更新最大子串长度`ret_val`...
我们需要找到这两个字符串的最长公共子序列,即在不改变顺序的情况下,X和Y共有的最长子串。在本例中,最长公共子序列是BCBA。 动态规划解决方案通常使用一个二维数组L[i, j],其中L[i, j]表示字符串X的前i个字符和...
4. **回文子串**:找到字符串中最长的回文子串,后缀数组结合Manacher's Algorithm等方法可以高效求解。 5. **连续重复子串**:寻找连续重复的子串及其出现次数,后缀数组同样适用。 6. **两个或多个字符串的相关...