关于华为机试题求代码！！！
n个字符串，1<n<20;找出n个字符串中相同的最长的子字符串；
如n=3
1.what is local bus？
2.this is local bus。
3.local bus is name sdhfj。
那么最长的共同子串是local bus
函数为char * findchar（const char**asd，const int n）
大体就是这些，用c去实现！！
大牛们 给力啊！！
[解决办法]
这样：先比较两个字符串， 找出所有互不包含的公共子串。
然后这堆子串再与第三个字符串相比，找出新的公共字串，，，
最后选出最长的那个。
[解决办法]
先两个字符串找 公共子串 。
然后拿公共子串和下一个字符串找 公共子串
往复循环，最后剩下的 公共子串 中找最长的 子串 返回。
最后没有剩下公共子串则返回NULL。
个人想法，估计这个贴会火，来顶一个..
[解决办法]
1、计算出 n 个字符串中最短的字符串a 的长度l， pos=0，len=l/2， n=1
2、从字符串a 的pos 位置取长度len 个字节
3、判断步骤2中的字节是否在其他n-1个字符串中
4、是，判断l/2^n是否为0，是，结束；否，len+=l/2^n，n++，回步骤2
5、否，判断pos>l-len，是，len-=l/2^n，n++，pos=0，回步骤2；否，pos++，回步骤2
6、从字符串a 的pos 位置取长度len 个字节作为返回值
[解决办法]
既然每个字符串都包含最长子字符串
1\选择 第1个和第2个字符串得到 最长子字符串a
2\选择 第3个和第4个字符串得到 最长子字符串b
3\从a b中得到最大子字符串c
4\选择 第5个和第6个字符串得到 最长子字符串d
5\选择 第7个和第8个字符串得到 最长子字符串e
6\从d e中得到最大子字符串f
从c f中得到子字符串。。。。g
。。。。。。。。。。。。。。。。。。。。。
[解决办法]
#include <iostream>#include <string>using namespace std;//将第一个字符串与最短的字符串交换void swap(string *pStr,int i){ string temp; temp = *pStr; *pStr = *(pStr + i); *(pStr + i) = temp;}int main(){ int N = 3; //cout << "请输入N(控制字符串个数):"; //cin >> N; //cout << "请输入" << N << "个字符串"<<endl; string *pStr; pStr = new string [N];//记录要查找的字符串 pStr[0] = "main what is local bus"; pStr[1] = "main this is local bus"; //pStr[2] = "local bus is name sdhfj"; pStr[2] = "main"; int i,min; int maxLen = 256; //找出输入的字符串中长度最小的串，并把最小串序号记在min中 for(i = 0; i < N; ++i){ // cin >> *(pStr + i); int len = (*(pStr +i)).length();// *操作符与调用函数的.操作符优先级问题，.优先级高于*，所以必须加上() if(len < maxLen){ maxLen = len; min = i; } } swap(pStr,min); /* for(i = 0; i < N; ++i) cout << *(pStr + i) << endl; */ int len0 = pStr[0].length(); int j,k,maxlen= 0; string maxStr; string tmpStr; for(i = 0; i < len0 && maxlen <= len0 - i -1; ++i) { for(j = 0; j < len0 && maxlen <= len0 - i -j - 1; ++j) { tmpStr = pStr[0].substr(i,len0 - j);//对字符串数组中第一个子串，求出其可能的子串值，如果剩余子串长度小于maxlen则不用去求了，for循环中给出了限制 //将子串tmpStr与参与匹配的字符串比较，判断tmpStr是否为剩余串的子串，如果不是则break出循环 for(k = 1; k < N; ++k) { string::size_type pos1 = pStr[k].find(tmpStr); if(pos1 < pStr[k].length()) continue; else break; } if(k == N)//说明子串tmpStr是其他参与匹配的子串的子串 { if(tmpStr.length() > maxlen)//tmpStr如果是当前最大的子串，则记录下来 { maxlen = tmpStr.length(); maxStr = tmpStr; } } } } cout << "最大公共子串为："; cout << maxStr <<endl; delete []pStr; return 0;}
[解决办法]
#include<string.h>
#include<stdio.h>
#include <stdlib.h>
#define M 100
char* LCS(char left[],char right[])
{ //LCS问题就是求两个字符串最长公共子串的问题
int lenLeft=strlen(left),lenRight=strlen(right),k;
//获取左子串的长度,获取右子串的长度
char *c=(char*)malloc(lenRight),*p;//注意这里要写成char型,而不是int型,否则输入整型数据时会产生错误。 //矩阵c纪录两串的匹配情况
//int c[M][M]={0};//当将c申明为一个二维数组时
int start,end,len,i,j;//start表明最长公共子串的起始点，end表明最长公共子串的终止点
end=len=0;//len表示最长公共子串的长度
for(i=0;i<lenLeft;i++)//串1从前向后比较
{ for(j=lenRight-1;j>=0;j--)//串2从后向前比较,为什么要从后向前呢?是把一维数组c[ ]当二维数组来用,
//如果要从前向后,可以将c申明为一个二维数组c[M][M].但程序要做相应调整.
// for(j=0;j<lenRight;j++)//当c申明为一个二维数组时
{ if(left[i] == right[j])//元素相等时
{ if(i==0||j==0)
c[j]=1;//c[i][j]=1;
else
{ c[j]=c[j-1]+1;//c[i][j]=c[i-1][j-1]+1;
}
}
else
c[j] = 0;//c[i][j]=0;
if(c[j] > len)//if (c[i][j]>len)
{ len=c[j];//len=c[i][j];
end=j;
}
}
}
start=end-len+1;
p =(char*)malloc(len+1);//数组p纪录最长公共子串
for(i=start; i<=end;i++)
{ p[i-start] = right[i];
}
p[len]='\0';
return p;
}
void main()
{ char str1[M],str2[M],str3[M];
printf("请输入字符串1:");
gets(str1);
printf("请输入字符串2:");
gets(str2);
// printf("请输入字符串3:");
// gets(str3);
printf("最长子串为:");
printf("%s\n",LCS(str1,str2));
//char *p=LCS(str1,str2);
// printf("%s\n",LCS(p,str3));
}
这是求两个字符串的最长相同子串，用的是一个二维矩阵的思想，求三个字符串的最长相同子串我觉得可以用三维数组了
[解决办法]
#include <iostream>
#include <string>
using namespace std;
//将第一个字符串与最短的字符串交换
void swap(string *pStr,int i)
{
string temp;
temp = *pStr;
*pStr = *(pStr + i);
*(pStr + i) = temp;
}
int main()
{
int N;
cout << "请输入N(控制字符串个数):";
cin >> N;
cout << "请输入" << N << "个字符串"<<endl;
string *pStr;
pStr = new string [N];
int i,min;
int maxLen = 1000;
//找出输入的字符串中长度最小的串，并把最小串序号记在min中
for(i = 0; i < N; ++i){
cin >> *(pStr + i);
int len = (*(pStr +i)).length();// *操作符与调用函数的.操作符优先级问题，.优先级高于*，所以必须加上()
if(len < maxLen){
maxLen = len;
min = i;
}
}
swap(pStr,min);
/*
for(i = 0; i < N; ++i)
cout << *(pStr + i) << endl;
*/
int len0 = pStr[0].length();
int j,k,maxlen= 0;
string maxStr;
string tmpStr;
for(i = 0; i < len0 && maxlen <= len0 - i -1; ++i)
{
for(j = 0; j < len0 && maxlen <= len0 - i -j - 1; ++j)
{
tmpStr = pStr[0].substr(i,len0 - j);//对字符串数组中第一个子串，求出其可能的子串值，如果剩余子串长度小于maxlen则不用去求了，for循环中给出了限制
//将子串tmpStr与参与匹配的字符串比较，判断tmpStr是否为剩余串的子串，如果不是则break出循环
for(k = 1; k < N; ++k)
{
string::size_type pos1 = pStr[k].find(tmpStr);
if(pos1 < pStr[k].length())
continue;
else
break;
}
if(k == N)//说明子串tmpStr是其他参与匹配的子串的子串
{
if(tmpStr.length() > maxlen)//tmpStr如果是当前最大的子串，则记录下来
{
maxlen = tmpStr.length();
maxStr = tmpStr;
}
}
}
}
cout << "最大公共子串为：";
cout << maxStr <<endl;
delete []pStr;
return 0;
}
#include <iostream>#include <string>#include <vector>using namespace std;void find(const string &str1, const string &str2, vector<string> &result){ typedef vector<string>::size_type size_t; typedef vector<string>::difference_type diff_t; result.clear(); size_t length = 0; const size_t length1=str1.length(), length2=str2.length(); for (size_t pos1=0; length1!=pos1; ++pos1) { for (size_t pos2=0; length2!=pos2; ++pos2) { diff_t diff=0; for (; pos1+diff != length1 && pos2+diff != length2 && str1[pos1+diff] == str2[pos2+diff]; ++diff) ; if (length < diff) { length = diff; result.clear(); result.push_back( str1.substr(pos1,diff) ); } else if (length == diff) { length = diff; result.push_back( str1.substr(pos1,diff) ); } } }}void findchar (char ** const asd, const size_t n){ if (n<1) return; if (n<2) { cout << asd[0] << endl; return; } vector<string> result; find(asd[0], asd[1], result); typedef vector<string>::const_iterator const_iter; for (size_t i=2; i!=n; ++i) { vector<string> list(result); for (const_iter beg=list.begin(), end=list.end(); beg != end; ++beg) { find(asd[i],*beg, result); } } for (const_iter beg=result.begin(), end=result.end(); beg != end; ++beg) { cout << *beg << endl; }}int main(){ char *asd[3]; char result[256]; char *str0="what is local bus?"; char *str1="this is local bus."; char *str2="local bus is name sdhfj."; asd[0] = str0; asd[1] = str1; asd[2] = str2; findchar (asd, 3); return 0;}