- 浏览: 1395332 次
- 性别:
- 来自: 广州
文章分类
最新评论
-
sdgxxtc:
[quo[color=red]te][/color]
C#使用OleDb读取Excel,生成SQL语句 -
zcs302567601:
博主,你好,一直都有个问题没有搞明白,就是 2.x的版本是通过 ...
NGUI所见即所得之UIPanel -
一样的追寻:
感谢楼主!
有向强连通和网络流大讲堂——史无前例求解最大流(最小割)、最小费用最大流 -
cp1993518:
感谢!从你的博客里学到了很多
Unity日志工具——封装,跳转 -
cp1993518:
学习了~,话说现在的版本custom还真的变委托了
NGUI所见即所得之UIGrid & UITable
题目:给定一个字符串,求其的最大回文子串。例如:字符串:owwoshisbsiha,它的最大回文子串是:hisbsih。
求解方法:暴力枚举、动态规划、后缀数组、线性算法
方法一:暴力枚举
最简单的方法当然就是对字符串的每一个子串进行回文判断。一个字符串有O(n²)个子串,然后判断是否回文复杂度是O(n),所以该算法的算法复杂度是O(n³)。
方法二:动态规划
动态规划之所以能改进算法是因为该算法保留之前计算过的情况,这样就后面的情况就能转化为在前面已有的结果上进行求解,这也是动态规划和递归的本质的区别。废话少说直接进入主题,我觉得解这个题目的一个很自然的想法就是从把字符串的每一字符当做回文子串的中心点向两边延伸来计算得到以该字符为中心的最长回文子串,如上面字符串以b为中心就会得到最长回文子串hisbsih,当然这里遇到回文子串长度是偶数(如:owwo)的还不能解决,稍后在说这个问题。假设现在有回文子串X了,那么sXs也是回文,如果X不是回文子串,则sXs也不能是回文。可以看出是以某点为中心子串长度从小到大顺序来构建最长回文子串。使用 dp[i][j] 记录字符串从位置i到位置j的回文子串长度,然后在用两个变量mx和str_begin分别记录最大回文子串的长度和回文子串的在字符串的起始位置。
下面来解决回文子串长度是偶数的解决方法:在字符与字符之间插入一个特殊字符如#,来间隔开字符,这样回文子串的长度都会变成奇数了。那就剩实现了,这个方法的关键是动态规划怎样进行两层循环,才能到达动态规划——转化为能使用前面结果的情况或者说是避免计算过的情况再次计算的效果。
第一层循环:回文子串的长度(二分之一)的从 1 到字符串长度的½
第二层循环:回文子串的中心点的移动
这样做,后面的情况才能在前面已有的结果上进行求解,当然还有初始化条件:dp[i][i]=1,其实i=0,1,…,n-1;其他值都初始化为0,初始化的意图是每一个中心点就是一个回文子串且长度为1。
╔
int mx; bool dp[SIZE][SIZE]={}; int str_begin=0; void LPS_dp(char * str, int length) // 略去测试X合法性 { maxlen = 1; for(int i = 0; i < length; ++i) // 初始化 { dp[i][i] = 1; // 单字符为回文 } for(int len = 1; len <= length; ++len) //长度 { for(int begin = 0; begin < length+1-len; ++begin) { int end = begin + len; // 从长度为2开始,首尾 if((X[begin]==X[end]) && (dp[begin+1][end-1]==1)) { dp[begin][end] = 1; if(end - begin + 1 > mx) { mx = end - begin + 1; str_begin=begin; } } } } }
╝①
动态规划的算法复杂度都是O(n²);这样也是减少重复计算的效果。
方法三:后缀数组
后缀数组,顾名思义就是从字符串某一个位置开始到结尾,例如:字符串dsqiu的后缀数组是dsqiu,sqiu,qiu,iu,u。然后对后缀数组进行排序(可以只以首字母来排序,规则可以自定义),排序之后后缀数组变为:dsqiu,iu,qiu,sqiu,u,排序的目的是方便进行枚举比较。
╔
后缀数组的应用:
例1:最长公共前缀
给定一个串,求任意两个后缀的最长公共前缀。
解:先根据rank确定这两个后缀的排名i和j(i<j),在height数组i+1和j之间寻找最小值。(可以用rmq优化)
例2:最长重复子串(不重叠)(poj1743)
解:二分长度,根据长度len分组,若某组里SA的最大值与最小值的差>=len,则说明存在长度为len的不重叠的重复子串。
例3:最长重复子串(可重叠)
解:height数组里的最大值。这个问题等价于求两个后缀之间的最长公共前缀。
例4:至少重复k次的最长子串(可重叠)(poj3261)
解:二分长度,根据长度len分组,若某组里的个数>=k,则说明存在长度为len的至少重复k次子串。
例5:最长回文子串(ural1297)
给定一个串,对于它的某个子串,正过来写和反过来写一样,称为回文子串。
解:枚举每一位,计算以这个位为中心的的最长回文子串(注意串长要分奇数和偶数考虑)。将整个字符串反转写在原字符串后面,中间用$分隔。这样把问题转化为求某两个后缀的最长公共前缀。
例6:最长公共子串(poj2774)
给定两个字符串s1和s2,求出s1和s2的最长公共子串。
解:将s2连接到s1后,中间用$分隔开。这样就转化为求两个后缀的最长公共前缀,注意不是height里的最大值,是要满足sa[i-1]和sa[i]不能同时属于s1或者s2。
例7:长度不小于k的公共子串的个数(poj3415)
给定两个字符串s1和s2,求出s1和s2的长度不小于k的公共子串的个数(可以相同)。
解:将两个字符串连接,中间用$分隔开。扫描一遍,每遇到一个s2的后缀就统计与前面的s1的后缀能产生多少个长度不小于k的公共子串,这里s1的后缀需要用单调栈来维护。然后对s1也这样做一次。
例8:至少出现在k个串中的最长子串(poj3294)
给定n个字符串,求至少出现在n个串中k个的最长子串。
解:将n个字符串连接起来,中间用$分隔开。二分长度,根据长度len分组,判断每组的后缀是否出现在不小于k个原串中。
求解后缀数组的算法主要有两种:倍增算法和DC3算法。
╝②
算法实现:
1.反转字符串,并连接到原字符串后面,以一个特殊字符串(‘#’)间隔;
2.得到后缀字符串数组,并对后缀字符串数组进行快速排序;
3.枚举后缀字符串数组求解最大公共前缀(最大公共前缀:字符串从开头相同的子串)。
下面附上网友的有关倍增算法和DC3算法的代码(没有测试)
倍增算法
╔
const int N = 20005;//串A的最大长度 const int MAX = 1000100;//串A的最大值 //int n,m,k; int SA[N], rank[N], height[N], key[N]; int A[N], C[MAX], t1[N+1], t2[N+1]; //倍增法求sa[]-----待排序的字符串放在r 数组中,r[]为整型数组, 从r[0]到r[n-1],长度为n,且最大值小于m //约定除r[n-1]外所有的r[i]都大于0, r[n-1]=0 //结果放在sa 数组中,从sa[0]到sa[n-1] //先对所有后缀的第一个字符进行排序(采用挖坑式的基数排序,即统计每个字符的个数,以便在扫描时总能将字符放入合适的位置),放入sa中 void da(int n, int m) { int i, j, l, s,*t; int *X = t1, *Y = t2; memset(C, 0, sizeof(C)); for (i=0;i<n;i++) C[X[i] = A[i]]++; for (i=1;i<m;i++) C[i] += C[i-1]; for (i=n-1;i>=0;i--) SA[--C[X[i]]] = i; for (l=1; l<n; l<<=1) { for (i=n-l,j=0;i<n;i++) Y[j++] = i; for (i=0;i<n;i++) if (SA[i] >= l) Y[j++] = SA[i] - l; for (i=0;i<n;i++) key[i] = X[Y[i]]; memset(C, 0, sizeof(C)); for (i=0;i<n;i++) C[key[i]]++; for (i=1;i<m;i++) C[i] += C[i-1]; for (i=n-1;i>=0;i--) SA[--C[key[i]]] = Y[i]; t = X; X = Y; Y = t; X[SA[0]] = j = 0; for (i=1;i<n;i++) { if (Y[SA[i]] != Y[SA[i-1]] || Y[SA[i]+l] != Y[SA[i-1]+l]) j++; X[SA[i]] = j; } m = j + 1; if (m==n) break; } for (i=0;i<n;i++) rank[SA[i]] = i; return; } //height[i]:suffix(sa[i-1])与suffix(sa[i])的最长公共前缀,即排名相邻的两个后缀的最长公共前缀 void calheight(int n) { int i,j,k=0; for(i=0; i<n; i++) { if (k > 0) --k; if(rank[i] == 0) height[0] = 0; else { j = SA[rank[i] - 1]; while(A[i+k] == A[j+k]) k++; height[rank[i]] = k; } } } //串A[0]...A[n-1] da(n,1000001); //m的最大值不超过1,000,000 calheight(n);
╝②
DC3算法
╔
#include "stdio.h" #include "string.h" #define maxn 2004 #define F(x) ((x)/3+((x)%3==1?0:tb)) #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2) int wa[maxn],wb[maxn],wv[maxn],ws[maxn]; int c0(int *r,int a,int b) {return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];} int c12(int k,int *r,int a,int b) {if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1); else return r[a]<r[b]||r[a]==r[b]&&wv[a+1]<wv[b+1];} void sort(int *r,int *a,int *b,int n,int m) { int i; for(i=0;i<n;i++) wv[i]=r[a[i]]; for(i=0;i<m;i++) ws[i]=0; for(i=0;i<n;i++) ws[wv[i]]++; for(i=1;i<m;i++) ws[i]+=ws[i-1]; for(i=n-1;i>=0;i--) b[--ws[wv[i]]]=a[i]; return; } void dc3(int *r,int *sa,int n,int m) { int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p; r[n]=r[n+1]=0; for(i=0;i<n;i++) if(i%3!=0) wa[tbc++]=i; sort(r+2,wa,wb,tbc,m); sort(r+1,wb,wa,tbc,m); sort(r,wa,wb,tbc,m); for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++) rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++; if(p<tbc) dc3(rn,san,tbc,p); else for(i=0;i<tbc;i++) san[rn[i]]=i; for(i=0;i<tbc;i++) if(san[i]<tb) wb[ta++]=san[i]*3; if(n%3==1) wb[ta++]=n-1; sort(r,wb,wa,ta,m); for(i=0;i<tbc;i++) wv[wb[i]=G(san[i])]=i; for(i=0,j=0,p=0;i<ta && j<tbc;p++) sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++]; for(;i<ta;p++) sa[p]=wa[i++]; for(;j<tbc;p++) sa[p]=wb[j++]; return; } int rank[maxn],height[maxn]; void calheight(int *r,int *sa,int n) { int i,j,k=0; for(i=1;i<=n;i++) rank[sa[i]]=i; for(i=0;i<n;height[rank[i++]]=k) for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++); return; } int RMQ[maxn]; int mm[maxn]; int best[20][maxn]; void initRMQ(int n) { int i,j,a,b; for(mm[0]=-1,i=1;i<=n;i++) mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1]; for(i=1;i<=n;i++) best[0][i]=i; for(i=1;i<=mm[n];i++) for(j=1;j<=n+1-(1<<i);j++) { a=best[i-1][j]; b=best[i-1][j+(1<<(i-1))]; if(RMQ[a]<RMQ[b]) best[i][j]=a; else best[i][j]=b; } return; } int askRMQ(int a,int b) { int t; t=mm[b-a+1];b-=(1<<t)-1; a=best[t][a];b=best[t][b]; return RMQ[a]<RMQ[b]?a:b; } int lcp(int a,int b) { int t; a=rank[a];b=rank[b]; if(a>b) {t=a;a=b;b=t;} return(height[askRMQ(a+1,b)]); } char st[maxn]; int r[maxn*3],sa[maxn*3]; int main() { int i,n,len,k,ans=0,w; scanf("%s",st); len=strlen(st); for(i=0;i<len;i++) r[i]=st[i]; r[len]=1; for(i=0;i<len;i++) r[i+len+1]=st[len-1-i]; n=len+len+1; r[n]=0; dc3(r,sa,n+1,128); calheight(r,sa,n); for(i=1;i<=n;i++) RMQ[i]=height[i]; initRMQ(n); for(i=0;i<len;i++) { k=lcp(i,n-i); if(k*2>ans) ans=k*2,w=i-k; k=lcp(i,n-i-1); if(k*2-1>ans) ans=k*2-1,w=i-k+1; } st[w+ans]=0; printf("%s\n",st+w); return 0; }
╝③
拓展
后缀数组的算法复杂度是O(n㏒n),主要是由排序引起的。那么,就会想到要是不经过排序的过程或者在构建后缀数组的过程就已经排好序,算法复杂度就会降到O(n)。这就得使用后缀树来完成构建后缀子串,这里后缀树就是子串中每一个字符都是后缀树的一个节点,如果两个前缀一样那么它们就拥有共同父亲节点。在构建后缀树的过程就记录从当前节点开始的最长公共前缀的长度,构建完成之后只要遍历一遍后缀树找到最长公共前缀,就是要找的最大回文子串的一半(如最长回文子串是abcdcba,得到的最长公共前缀是abcd)。这里说的比较简单,不过我觉得看到这里的理解应该都没问题吧,当然后缀树还有很多应用(如数据挖掘的FP-Growth Algorithm的FP tree)。
更多分析可以阅读参考④的内容。
方法四:线性算法
算法复杂度要尽可能小,一个优化方法就是避免之前情况的重复计算,正如前面动态规划对暴力枚举的改进——保留之前已经计算过的情况的结果,后面的情况转为在前面记录基础之上来算。无所不用其极,自然会想在动态规划有没有将已经计算结果充分利用殆尽。还是可以发现还有一个特征没有被利用,动态规划只保留前面情况的结果(利用仅此而已),其实真正的主角——回文还没有利用,就是只利用了回文子串的是不是的结果,但是没有利用回文子串对称的结果。
用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度,增加两个辅助变量(其实一个就够了,两个更清晰)id和mx,其中id表示最大回文子串中心的位置,mx则为id+P[id],也就是最大回文子串的边界。
在计算以第 i 位置的字符为中心的最长回文子串时,所有在 i 前面的情况都计算过了,换而言之,p[j]都是已知,当j<i的时候,那么就充分利用这个性质吧。
看下图中,现在计算以第 i 位置的字符为中心的最长回文子串,前面已有的结果是最长回文子串的中心位置是 id 长度为 mx,j 是 i 关于 id 的对称点,如果mx>i,那么 i 就可以获得一个已知的回文子串的长度,即p[j]的值,就是在 j 的回文子串在 i 处同样会出现(对称嘛),这样就不用像动态规划那样每个位置begin的len都从1开始增大,而是直接从p[j]开始。
算法实现:
╔
/* O(n)解法 */ #define MIN(a,b) ((a) < (b) ? (a) : (b)) int mx; int maxid; // 最长回文子串下标 int LPS_rb[100]; // i为中心的回文子串右边界下标right border char str[100]; // 原字符串处理后的副本 void LPS_linear(char * X, int xlen) { mx= maxid = 0; str[0] = '$'; // 将原串处理成所需的形式 char *p = str; *(++p)++ = '#'; while((*p++ = *X++) != '\0') { *p++ = '#'; } for(int i = 1; str[i]; ++i) // 计算LPS_rb的值 { if(maxlen > i) // 初始化LPS[i] { LPS_rb[i] = MIN(LPS_rb[2*maxid-i],(mx)); }else { LPS_rb[i] = 1; } while(str[i-LPS_rb[i]] == str[i+LPS_rb[i]]) // 扩展 { ++LPS_rb[i]; } if(LPS_rb[i]-1-i > mx) { mx = LPS_rb[i]-1-i; maxid = i; } } } 给出测试用例: void main() { char X[30]; // 设串不超过30 /* test case * aaaa * abab */ while(cin.getline(X,30)) { /* 后缀数组方法 */ LPS_suffix(X,strlen(X)); printf("%d\n", maxlen); /* O(n)方法 */ LPS_linear(X,strlen(X)); printf("%d\n", maxlen); } }
╝④
小结:
至此,将四种方法全面列举完毕,我觉得至少看出算法优化的一个范例,算法优化无非就是穷尽事物特征,无所不用其极,如果你有任何建议或者批评和补充,请留言指出,不胜感激,更多参考请移步互联网。
类似问题
最大公共子串,最大公共子序列,最长重复子串,最长不重复子串,最长递增序列,最大子数组和
参考:
①勇幸|Thinking: http://www.ahathinking.com/archives/132.html
②yzmduncan: http://yzmduncan.iteye.com/blog/979771
③小阮的菜田: http://www.cppblog.com/jericho/archive/2011/06/30/149862.aspx
④O興~: http://imlazy.ycool.com/post.2011818.html
⑤ felix021: http://www.felix021.com/blog/read.php?2040
评论
1 最后一种方法LPS_linear中22-24行是否应该写成如下:
if(maxlen+maxid > i) // 初始化LPS[i]
{
LPS_rb[i] = MIN(LPS_rb[2*maxid-i],(maxlen+maxid-i));
2 另外该程序貌似没有声明全局变量maxlen
3 24行取最小值这一步感觉楼主在解释的时候没有解释充分,读者在这里理解起来还是有点费劲。
首先谢谢你的指出,maxlen是没有声明,因为有时候贴出来的代码只是全部代码的部分,会有遗漏,其次,这里的maxlen是指当前最长回文子串的串尾在原字符串的位置,而不是图中的mx,第三个问题看到这里应该就没有问题了吧,谢谢!
1 最后一种方法LPS_linear中22-24行是否应该写成如下:
if(maxlen+maxid > i) // 初始化LPS[i]
{
LPS_rb[i] = MIN(LPS_rb[2*maxid-i],(maxlen+maxid-i));
2 另外该程序貌似没有声明全局变量maxlen
3 24行取最小值这一步感觉楼主在解释的时候没有解释充分,读者在这里理解起来还是有点费劲。
发表评论
-
C#使用OleDb读取Excel,生成SQL语句
2013-06-27 15:47 9941C#使用OleDb读取Excel,生成SQL语句 ... -
C#读写XML文件工具类——满足一切需求
2013-06-18 07:33 10692C#读写XML文件工具类— ... -
C#解析XML
2013-06-17 19:20 0覆盖 -
C#读取Excel数据动态生成对象并进行序列化
2013-06-16 20:10 7860C#读取Excel数据 ... -
Unity导入unitypackage总是失败问题原因
2013-06-11 22:54 11403最近尝试手游开发,用的Unity引擎,然后开 ... -
C# socket连接服务器发送和接收数据在设置断点单步执行没有问题但是直接运行不能成功
2013-06-04 20:26 5861题目有点长, ... -
C# 调用Delegate.CreateDelegate方法出现“未处理ArgumentException”错误解决
2013-05-31 12:24 3467在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 2252Java学习笔记整理 ... -
Java学习笔记整理
2012-11-24 23:43 211Java学习笔记整理 本文档是我个人 ... -
《C++必知必会》学习笔记
2012-11-24 23:40 2558《C++必知必会》学 ... -
《C++必知必会》学习笔记
2012-11-24 23:34 1《C++必知必会》学习笔 ... -
Java文件输出时,文件大小只有24KB
2012-11-14 22:10 1530今天,用Java做点事情,出现了一个很莫名其妙的事情就是文件 ... -
C语言名题精选百则——游戏问题
2012-11-05 23:27 86第8章游戏问题 问题8.1苞数阶魔方阵(MAGIC_O ... -
C语言名题精选百则——序曲
2012-11-04 23:27 2311C语言名题精选百则——序曲 ... -
C语言名题精选百则——数字问题
2012-11-04 23:25 3961C语言名题精选百则——数字问题 尊重他人的劳动, ... -
C语言名题精选百则——排序
2012-11-04 23:29 128第5章排 序 问题5.1 二分插入法(BIN ... -
C语言名题精选百则——查找
2012-11-04 23:29 4023尊重他人的劳动,支持原创 本篇博文,D.S.Q ...
相关推荐
主要为大家详细介绍了python实现对求解最长回文子串的动态规划算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
Manacher算法:求解最长回文字符串,时间复杂度为O(N) 回文串定义:“回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。回文子串,顾名思义,即字符串中满足回文性质的子串。
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1: 输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。 示例 2: 输入: “cbbd” 输出: “bb” 思路 基于中心...
最长公共子串求解,有需要的可以下来参考……
求解最大子序列、最长递增子序列、最长公共子串、最长公共子序列. http://blog.csdn.net/ssuchange/article/details/17341693
最长公共子串(The Longest Common Substring) LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1...
若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有...给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最长公共子序列
主要介绍了PHP实现求解最长公共子串问题的方法,简单描述了求解最长公共子串问题算法原理,并结合实例形式分析了PHP实现求解最长公共子串的具体操作技巧,需要的朋友可以参考下
如果头尾对应相同,则回文序列求解递归求解去头尾的回文序列(X...X => ...); 如果头尾对应不同,则有两种情况, 一种是在尾部后面添加头(X...Y => X...YX => ...Y), 一种是在头部前面添加尾(X...Y => YX...Y => X....
一、问题描述 子串应该比较好理解,至于什么是子序列,这里给出一个例子...在上述例子的中,最长公共子序列为blog(cnblogs, belong),最长公共子串为lo(cnblogs, belong)。 二、求解算法 对于母串X=<x1,x2,⋯,xm
最长回文子串(lps) ###幂乘:算法复杂度是O(lgn) ##贪心算法 活动选择问题 带权活动选择问题(其实就是一个调度问题) 分数背包问题 ###斐波那契树 使用循环实现的算法o(n) ##数论算法 欧几里得算法求解最大公约数...
前面一篇PHP实现求解最长公共子串问题的方法是基于java改进而来,这里再来看另一种公共子串算法。 代码如下: <?php $a = 'abceee12345309878'; $b = 'abceeew2345i09878fsfsfsfabceeewsfsdfsfsabceeew'; $c = ...
最长回文子串 让代码 819 最常用的词 让代码 937 重新排序日志文件 斯威亚 4861 回文 斯威亚 4864 字符串比较 斯威亚 4865 字符数 03. 堆栈 来源 不。 问题 关联 代码 程序员 塔 程序员 货车过桥 程序员 功能开发 ...
详细介绍了怎么在线性空间下求解最长公共子序列
动态规划求解最长回文子串 3 hmm 前向计算法,结合hanlp博客与李航的统计学一起看的 9月19日 1 句法依存分析以及语法树 2 leetcode双指针盛最多水问题 3 hmm 维特比算法 4 jupyter notebook 写文档 9月20日 1 ...
关于动态规划求解最长公共子序列的方法,讲得蛮清楚的。
C语言入门回文数求解
最长公共子序列及杭电1394的求解 求解字符串公共子串的问题
题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个函数,输入两个字符串,...