C語言實(shí)現(xiàn)：
窮舉法：
#include <iostream.h>//窮舉法計(jì)算最大公共子字符串
#define M 100
typedef struct
{
?char str[M];
?int length;
}seqstring;
int len_link(seqstring p)
{
?int i=0,length=0;
?while(p.str[i]!='\0')
?{
??i++;
??length++;
?}
?return (length);
}
void same(seqstring p,seqstring s)
{
?seqstring r;
?int i=0,l,m,n=0,k;
?while(i<p.length)//用窮舉法求最大公共子字符串
?{
??int j=0;
??while(j<s.length)
??{
???if(p.str[i]==s.str[j])//以p為基準(zhǔn)
???{
????l=1;
????for(m=1;i+m<p.length&&j+m<s.length&&p.str[i+m]==s.str[j+m];m++)//尋找相等的
????{
?????l++;//記錄相等字符的個(gè)數(shù)
????}
????if(l>n)
????{
????? k=i;//記錄公共字符串的起點(diǎn)位置
????? n=l;//記錄公共字符串的個(gè)數(shù)
????}
?????j=j+l;
???}
???else
???{
????j++;
???}
?? }
??? i++;
?}
?if(n>0)
?{
??for(i=0;i<n;i++)
??{
???r.str[i]=p.str[i+k];
???r.length=n;
??}
?}
?else
?{
??cout<<"無!";
?}
? for(i=0;i<n;i++)
? {
??cout<<r.str[i];
? }
?cout<<endl;
}
void main()
{
? seqstring p,s;//結(jié)構(gòu)體
? cout<<"請輸入第一個(gè)字符串元素:";
? cin>>p.str;
? cout<<"請輸入第二個(gè)字符串元素:";
? cin>>s.str;
? p.length=len_link(p);
? s.length=len_link(s);
? cout<<"最大公共子串為:";
? same(p,s);
}
java語言實(shí)現(xiàn)：
基本思想是從最大字符串開始比較
先選擇兩個(gè)字符串中 較小的一個(gè)并以其為基準(zhǔn)? 然后由大開始向小進(jìn)行比較 找到的第一個(gè)就是最大的。
import java.sql.DriverManager;
public class Abc {
?
?? public?? static?? String?? getSubString(String?? s1,?? String?? s2)?? {??
??? if?? (s1.length()?? >?? s2.length())?? {??
??? String?? temp?? =?? s1;??
??? s1?? =?? s2;??
??? s2?? =?? temp;??
??? }??
??? int?? n?? =?? s1.length();??
??? int?? index?? =?? 0;??
??? ok:? for?? (;?? n?? >?? 0;?? n--)?? {??
??? for?? (int?? i?? =?? 0;?? i?? <?? s1.length()?? -?? n?? +?? 1;?? i++)?? {??
??? String?? s?? =?? s1.substring(i,?? i?? +?? n);??
??? if?? (s2.indexOf(s)?? !=?? -1)?? {??
??? index?? =???? i;??
??? break?? ok;??
??? }??
??? }??
??? }??
??? return?? s1.substring(index,?? index?? +?? n);??
??? }
??public static void main(String[] args) throws Exception {
???String a="abnajfkabcdefghijklmnkajftwtlkwrejtrewq";
???String b="jljafabcdefghijklmnlkfjieoijjflja";
???
???String result=getSubString(a,b);
???System.out.println("result============="+result);
??
??}
}