- 浏览: 1397297 次
- 性别:
- 来自: 广州
文章分类
最新评论
-
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 9959C#使用OleDb读取Excel,生成SQL语句 ... -
C#读写XML文件工具类——满足一切需求
2013-06-18 07:33 10705C#读写XML文件工具类— ... -
C#解析XML
2013-06-17 19:20 0覆盖 -
C#读取Excel数据动态生成对象并进行序列化
2013-06-16 20:10 7877C#读取Excel数据 ... -
Unity导入unitypackage总是失败问题原因
2013-06-11 22:54 11416最近尝试手游开发,用的Unity引擎,然后开 ... -
C# socket连接服务器发送和接收数据在设置断点单步执行没有问题但是直接运行不能成功
2013-06-04 20:26 5877题目有点长, ... -
C# 调用Delegate.CreateDelegate方法出现“未处理ArgumentException”错误解决
2013-05-31 12:24 3477在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 2259Java学习笔记整理 ... -
Java学习笔记整理
2012-11-24 23:43 211Java学习笔记整理 本文档是我个人 ... -
《C++必知必会》学习笔记
2012-11-24 23:40 2572《C++必知必会》学 ... -
《C++必知必会》学习笔记
2012-11-24 23:34 1《C++必知必会》学习笔 ... -
Java文件输出时,文件大小只有24KB
2012-11-14 22:10 1543今天,用Java做点事情,出现了一个很莫名其妙的事情就是文件 ... -
C语言名题精选百则——游戏问题
2012-11-05 23:27 86第8章游戏问题 问题8.1苞数阶魔方阵(MAGIC_O ... -
C语言名题精选百则——序曲
2012-11-04 23:27 2317C语言名题精选百则——序曲 ... -
C语言名题精选百则——数字问题
2012-11-04 23:25 3975C语言名题精选百则——数字问题 尊重他人的劳动, ... -
C语言名题精选百则——排序
2012-11-04 23:29 128第5章排 序 问题5.1 二分插入法(BIN ... -
C语言名题精选百则——查找
2012-11-04 23:29 4033尊重他人的劳动,支持原创 本篇博文,D.S.Q ...
相关推荐
寻找最长不重复子串 python代码
7-6 最长对称子串 (25分) 对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最长对称子串为s PAT&TAP s,于是你应该输出11。 输入格式: 输入在一行中给出长度不超过1000的...
最长公共子串求解,有需要的可以下来参考……
在字符串中查找最长重复子串的探讨 写一个函数,找出一个字符串中最长的重复子串。“t1t1”结果就是t1."cabcabca"结果就是cab或者abc或者bca。
在随意给出的2个字符串中,找出它们共同的最长的子串。 【输入】 输入文件的第一行为一个整数2,接下来有2行,每行为一个字符串,每个字符串的长度均小于255。 【输出】 输出只有一行,即:共同的最长子串,若有多个...
最长公共子串的快速搜索算法 最长公共子串的快速搜索算法 最长公共子串的快速搜索算法
输入一个字符串,求出其中最长的回文子串。子串的含义是:在原串中连续出现的字符串片段。回文的含义是:正着看和倒着看相同,如abba和xyyxyyx。在判断时,应该忽略所有标点符号和空格,且忽略大小写,但输出应该...
最长回文子串
求解最大子序列、最长递增子序列、最长公共子串、最长公共子序列. http://blog.csdn.net/ssuchange/article/details/17341693
查找两个字符串a,b中的最长的公共子串,并将结果输出
最长回文子串,算法还算可以,能运行通过,运行时间也不长
用定长顺序存储结构表示串: (1) 建立两个文本文件,分别存储串str1“hellohisgoodl”和串str“hellogdygoodl” (2) 输出两个串的最长公共子串“hello”和“goodl”; (3) 分析算法时间复杂度。
本文实例讲述了C语言求两个字符串的最长公共子串的方法。分享给大家供大家参考。具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * ...
大整数计算器最长公共子串数据结构课设,沈阳工程学院
求两个字符数组的最长公共子串的问题,使用动态规划法,java语言实现。
输入一个字符串,将输出该字符串最长对称子串及其长度,很精巧的算法
自己编的,望大家指点!这是西工大期末考试的题目,做了好久才做出来
动态规划:最长公共子串 LCS 动态规划:最长公共子串 LCS
leetcode刷题宝典
本文实例讲述了JavaScript自定义函数实现查找两个字符串最长公共子串的方法。分享给大家供大家参考,具体如下: //查找两个字符串的最长公共子串 function findSubStr(s1,s2){ var S=sstr= ,L1=s1.length,L2=s2....