from: http://blog.csdn.net/jianzhibeihang/article/details/4985276
在版里看到有人问最大公共字串的问题，自己学习后在这里将总结发出来。最大公共字串分为两类，一类是我们大家所熟知的两个字符串的最大公共子串，另一个是我在搜索中发现的就是N个字符串的最大公共字串问题。
首先来看两个字符串的最大公共字串问题。这里我列出了两种解法，第一种就是暴力解法，第二种是动态规划来解的。还有一种解法就是我们数据结构书上会降到的
KMP匹配算法，这里我没给出。
第一种：暴力解法（c语言实现的）
#include<stdio.h> #include<stdlib.h> #include<string.h> char* longest(char *a,char *b) { int alen = strlen(a); int blen = strlen(b); int i,j,index,max=0,num=0; int start; for(i = 0; i < alen; i++) { for(j = 0; j < blen; j++) { //这里的start1、start2是比较关键的 int start1=i; int start2=j; while((start1 <= alen-1) && (start2 <= blen-1) && (a[start1++] == b[start2++])) num++; if(num > max)//如果num是当前最大匹配的个数，则赋给max，并且在start记下str1最长匹配开始的位置 { max=num; start=i; } num=0;//如果num不是当前最大的，则赋为0值继续循环 } } char *str=(char *)malloc(max + 1); strncpy(str,a + start,max);//从字符串a的start位置开始，拷贝max个字符到str中，这就是我们找出的最大子串 str[max] = '/0'; return str; } int main() { char a[]="abcdabcdcbadffdaccccafg"; char b[]="gfaccccadffdabcdcbadcba"; char *str; str = longest(a,b); printf("%s/n",str);
free(str); //之前这里忘记free了，造成内存泄露了 system("pause"); return 0; }
第二种，动态规划解法（c++实现的）这里主要是定义了一个sign数组，这个数组用来保存str1中每个字符向前能与str2中的字符匹配的个数。每次会将最大的匹配个数保存到max变量中，并且用end来记录拥有max的字符在原字符串中的位置。
#include <iostream> #include <string> using namespace std; string lcs_search(string str1, string str2) { int length = 0; int end = 0; if (str1.length() < str2.length()) //保证str1为母串（较长的哪个串) { string strTemp = str1; str1 = str2; str2 = strTemp; } int * sign = new int[str1.length()]; //sign里存储的是母串（str1）每个元素前向能与子串匹配的公共子串数 //比如sign[12]==5;则说明从str1[12]往前(所以在第二个for循环中j的计数就是从str1的最后一个开始)5个元素(包括[12])， //能与str2的某一段匹配 for (int i = 0; i < str2.length(); i++) { for (int j = str1.length() - 1; j >= 0; j-- ) { if (str2[i] == str1[j]) { if (i == 0 || j == 0) //i==0，则母串的j元素必然只能匹配一个，j==0同理 sign[j] = 1; else //由于该次j匹配，所以子串可以+1 sign[j] = sign[j - 1] + 1; } else //不匹配，则此位置的sign归零 sign[j] = 0; if (sign[j] > length) //结果存储 { length = sign[j]; end = j; } } } delete []sign; return str1.substr(end - length + 1, length); } int main() { string a="123456789abcdefghijklmn2131.dfdfdf",b="123456sdkk123456789abcddkfdfkd123456789abcde"; string c; c=lcs_search(a,b); cout<<c<<endl; return 0; }
N个字符串的最大公共子串：
整个程序的思路如下：
第一步，首先从所有的输入参与匹配的字符串中，选出长度最小的串放在字符串数组中第一的位置，swap函数就是用于交换的
第二步，拿长度最小的字符串开刀，两个for循环用于控制并求出最小字符串的子串，比如对bbcdef，子串序列是bbcdef、bbcde、bbcd、bbc、bb……
如果剩余的的长度小于maxlen则没必要继续求下去了，详情见两个for循环
第三步，对于求出来的每个子串，与剩余的参与匹配的字符串匹配，利用字符串自带的find函数来确定tmpStr是否是剩余字符串的子串。以此来找出最大的公共子串。
源代码：
#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; }