基于字符串的最大子串问题是经常面试的问题，想要表现的好不但要会基础的方法，同时还要学会优化的算法。
常考的有两个问题：
1：两个字符串的最大公共子串（还可能是子序列）
2：同一个字符串中相同的最大子串问题
例如输入qweabcuwabcfw,输出结果为：重复字符串的长度3和位置4
一：求两个字符串的最大公共子串
|
#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
char out[50];
vector<string> re;
int longestSubstring1(string x, string y,int &start) {
int xlen = x.size();
int ylen = y.size();
if (xlen == 0 || ylen == 0) {
return 0;
}
int max = -1;
//暴力破解法，两重for循环加 while
for (int i = 0; i < xlen; i++) {
for (int j = 0; j < ylen; j++) {
int m = i, n = j;
int len = 0;
while (m < xlen && n < ylen) {
if (x[m] != y[n]) {
break;
}
m++;
n++;
len++;
}
if (len > max) {
max = len;
start = i;
}
}
}
return max;
}
//动态规划
int longestSubstring2(string x, string y,int &start) {
//设置dp数组
vector<vector<int> > f(x.size() + 1, vector<int>(y.size() + 1, 0));
//vector< vector<int> > f;
int max = -1;
for (int i = 1; i <= x.size(); i++) {
for (int j = 1; j <= y.size(); j++) {
if (x[i - 1] != y[j - 1]) f[i][j] = 0;
else if (x[i - 1] == y[j - 1]) f[i][j] = f[i - 1][j - 1] + 1;
if (max < f[i][j]) {
max = f[i][j];
start = i;
}
}
}
return max;
}
int main()
{
string x = "adbccadbxadebbca";
string y = "bcadrbxad";
int start;
int out =longestSubstring1 (x,y,start);
cout << out << "-" << start << endl;
for (int i=0; i<out ;++i)
cout << x[start + i];
cout << endl;
cout << longestSubstring2(x,y,start) <<"-" << start;
return 0;
} |
2:c语言的写法
| #include<iostream>
#include<string.h>
#include<vector>
using namespace std;
char out[50];
vector<int> myvector;
int fun(char* a , char *b)
{
int len_a = strlen(a);
int len_b = strlen(b);
if(len_a<=0||len_b<=0)
return -1;
char * c , *d;
if(len_a<len_b)
{
c = b;
d = a;
}
else
{
c =a ;
d =b;
}
int max =0;
for( ; *c!='\0';c++ )
{
int n = 0; //n是个遍历指针，判断首字母是否相等
for( ;*(d+n)!='\0'; ++n)
{
if(*c !=*(d+n))
{
continue;
}
else
{
int len =0;
while(*(c+len)!='\0'&&*(c+len)==*(d+n+len)&&*(d+n+len)!='\0')
{
len++;
}
if(len>max)
{
max =len;
{
for( int m=0;m <max;m++)
{
out[m]=*(c+m);
}
out[max]='\0';
}
}
}
}
}
return max;
} int main()
{
char a[] ="adbccadbxadebbca";
char b[]= "bcadrbxad";
int len =fun(a,b);
cout << out << endl;
//cout << 0;
return 0; } |
还有别人的一个递归的解法，没看太懂，贴出来你们欣赏吧！
| #include <iostream>
#include <string>
#include <memory.h>
#include <stdio.h>
#include <stdlib.h>
//#include <windows.h>
using namespace std;
char findMaxStr(char * s1,char *s2){
char *ss;
static int maxlen=0;
int len;
if(strstr(s1,s2)) //如果S2是S1的子串
{
if(maxlen<strlen(s2))
{
maxlen=strlen(s2);
printf("maxlen:%d result:%s\n",maxlen,s2);
}
return 0;
}
len=strlen(s2);
if(len==1)
{ //递归的出口函数，终止条件
//printf("error\n");
//return 1;
return 1;
}
ss=(char *)malloc(len);
memcpy(ss,s2,len);//内存拷贝函数
ss[len-1]=0;
//printf("len=%d str=%s\n",len-1,ss);
findMaxStr(s1,ss); //是否需要注释掉？？
memcpy(ss,s2+1,len); //后移一位
//printf("second: len=%d str=%s\n",len-1,ss);
findMaxStr(s1,ss); //递归
free(ss);
return 1;
}
int main()
{
char a[200]="adcyioabcdefxxabcdxxx";
char b[200]="mxx0";
findMaxStr(a,b);
return 0;
}
|
二：字符串的最长公共子串
这实质上是第一道题的变形，例如输入qweabcuwabcfw,输出结果为：重复字符串的长度3和位置4
第一种解法：以字符串的长度为外循环，内循环从字符串的第一个元素开始向后移动。
| #include<iostream>
#include<string>
using namespace std;
int main()
{
string str, tep;
cout << "输入字符串" << endl;
cin >> str;
cout <<str.size()<<endl;
int mysize = str.size();
int k =0;
int max =0;
int first;
for (int i = 1; i <mysize; i++)
{
for (int j = 0; j < mysize-i; j++)
{
if (str[j]==str[j+i])
{
k++;
}
else
{
k=0;
}
if(k>max)
{
max = k;
first =i-k+1;
}
}
}
cout << first << "-" << max <<endl;
return 0; } |
第二种解法
题目：输入一行字符串。找出当中出现的同样且长度最长的字符串，输出它及其首字符的位置。
比如：“yyabcdabjcabceg"，输出结果应该为abc 和3.
#include<iostream>
#include<string>
using namespace std;
int main()
{
string str, tep;
cout << "输入字符串" << endl;
cin >> str;
for (int i = str.length() - 1; i > 1; i--)
{
for (int j = 0; j < str.length(); j++)
{
if (j + i <= str.length())
{
size_t t = 0;
size_t num = 0;
tep = str.substr(j, i);//从大到小取子串，从j位置开始取长度为i的子串
t = str.find(tep);//正序查找
num = str.rfind(tep);//逆序查找
if (t != num)//假设两次查找位置不一致，说明存在反复子串
{
cout << tep << " " << t + 1 << endl;//输出子串及位置
system("pause");
return 0;
}
}
}
}
}
substr(j, i);//从大到小取子串，从j位置开始取长度为i的子串
t = str.find(tep);//正序查找
num = str.rfind(tep);//逆序查找
if (t != num)//假设两次查找位置不一致，说明存在反复子串
{
cout << tep << " " << t + 1 << endl;//输出子串及位置
system("pause");
return 0;
}
}
}
}
}