1. 题目：输入一个字符串，要求找出字符串中最大子串的长度(如字符串abcd13agbf，当重复出现某个字符时，算一个子串，比如abcd13a或bcd13agb都是子串)。
理解：要是每个字符都不一样，则最大子串长度为0
思想：用空间换取时间，用一个数组lastPos[256]代表着256个可能的字符（ASC2码），而数组的值代表字符串中这个字符的最后出现位置，初始数组元素都为负数，然后每次取字符串中的一个字符，此字符的ASC2码为c，若lastPos[c]<0,则表示此字符第一次出现，置lastPos[c]为此字符在字符串中的位置，若lastPos[c]>=0,则表示此字符已经出现过，则可以计算这个子串的长度，若比之前的最大子串长，则更新最大子串长度。
分析：时间复杂度为o（n）遍历一次即可
int GetMaxSubStr(const unsigned char *str)
{
int maxLen = 0;
if (NULL == str)
return 0;
int lastPos[256]; //代表着256个可能的字符（ASC2码），数组元素值代表字符串中字符的最后出现的位置
for (int i = 0; i < 256; ++i)
lastPos[i] = -1;
for (int pos = 0; str[pos] != ' '; ++pos)
{
unsigned char c = str[pos];
if (lastPos[c] > -1) //此字符已经出现过
{
int len = pos - lastPos[c] + 1; //计算子串的长度
if (len > maxLen)
maxLen = len;
}
lastPos[c] = pos;
}
return maxLen;
}
2. 找出两个字符串中的最长相同子串
算法的思想：利用二维数组建立两个字串之间的“对应矩阵”，然后初始化矩阵（mat[i][j]置1或0），然后根据矩阵的对角线找出连续出现1的最长段，及在串中的起始位置。
如果只有两个字符串，可以先建一个二维数组（实际上用不到二维数组,下面再详细说），如input和reputation,如下：
i n p u t
r 0 0 0 0 0
e 0 0 0 0 0
p 0 0 1 0 0
u 0 0 0 2 0
t 0 0 0 0 3
a 0 0 0 0 0
t 0 0 0 0 1
i 1 0 0 0 0
o 0 0 0 0 0
n 0 1 0 0 0
其中的数字含义如下，0表示相应行和列的字符不相等，不是零就表示从这个字符开始，前n个字符是相同的，n就是那个数。比如第5列，第5行是3，表示input和reputation都有put这个子串。这些数里边有一个最大的，找出来就是了。
所以可以看出，对于两个字符串的问题，如果你不是想把所有的最长公共子串都找出来的话，可以逐行逐列地计算，只要在计算过程中保留最大值就可以了。
怎么"逐行逐列"地计算呢？可以先算第一行第一列，然后每一行每一列都通过上一行上一列算出。如果两个字符不相等，就为零。如果相等，就是左上角的数+1。因此算出了下一行和下一列，上一行和上一列就可以不要了。因为我们纵保存最大值，和产生最大值的位置。所谓动态规划，就是你算出下一行下一列，上一行上一列就可以不要了。
动态规划
private void printLCS(StringBuffer sb, int i, int j, String s1, int[][] flag) {
if (i == 0 || j == 0) {
return;
}
if (flag[i][j] == 1) {
printLCS(sb, i - 1, j - 1, s1, flag);
sb.append(s1.charAt(i - 1));
} else if (flag[i][j] == 2) {
printLCS(sb, i - 1, j, s1, flag);
} else {
printLCS(sb, i, j - 1, s1, flag);
}
}
public String calculateLCS(String s1, String s2) {
int[][] result = new int[s1.length() + 1][s2.length() + 1];
int[][] flag = new int[s1.length() + 1][s2.length() + 1];
for (int i = 0; i <= s1.length(); i++) {
result[i][0] = 0;
}
for (int i = 0; i <= s2.length(); i++) {
result[0][i] = 0;
}
for (int i = 1; i <= s1.length(); i++) {
for (int j = 1; j <= s2.length(); j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
result[i][j] = result[i - 1][j - 1] + 1;
flag[i][j] = 1;
} else if (result[i - 1][j] >= result[i][j - 1]) {
result[i][j] = result[i - 1][j];
flag[i][j] = 2;
} else {
result[i][j] = result[i][j - 1];
flag[i][j] = 3;
}
}
}
StringBuffer sb = new StringBuffer();
printLCS(sb, s1.length(), s2.length(), s1, flag);
String lcs = sb.toString();
return lcs;
}
public static void main(String[] args) {
String s1 = "ssssssssssssssssssssssssssssssss";
String s2 = "111sssss11ss";
LCS lcs = new LCS();
System.out.print(lcs.calculateLCS(s1, s2));
}
}
3. 在一个字符串中查找可能的最长子串，该子串由相同字符组成
#include <stdio.h>
#include <string.h>
void find(char* str, char*& start, int& length)
{
char* p = str;
char* q;
int len = 0;
length=0;
while(*p)
{
q = p+1;
while(*q && *q == *p)
q++;
len = q - p;
if(len>length)
{
length = len;
start = p;
}
p=q;
}
}
int main()
{
char str[1024];
scanf("%s", str);
char* p;
int len;
find(str,p, len);
p[len]=0;
printf("%s
", p);
return 0;
}
4. 给定一个字符串，输出最长的重复子序列
举例：ask not what your country can do for you,but what youcan do for your country
最长的重复子序列：can do for you
思路：使用后缀数组解决
分析：
1、由于要求最长公共子序列，则需要找到字符串的所有子序列，即通过产生字符串的后缀数组实现。
2、由于要求最长的重复子序列，则需要对所有子序列进行排序，这样可以把相同的字符串排在一起。
3、比较相邻字符串，找出两个子串中，相同的字符的个数。
注意，对于一个子串，一个与其重复最多的字符串肯定是紧挨着自己的两个字符串。
步骤：
1、对待处理的字符串产生后缀数组
2、对后缀数组排序
3、依次检测相邻两个后缀的公共长度
4、取出最大公共长度的前缀
举例：输入字符串 banana
1、字符串产生的后缀数组：
a[0]:banana
a[1]:anana
a[2]:nana
a[3]:ana
a[4]:na
a[5]:a
2、对后缀数组进行快速排序，以将后缀相近的（变位词）子串集中在一起
a[0]:a
a[1]:ana
a[2]:anana
a[3]:banana
a[4]:na
a[5]:nana
之后可以依次检测相邻两个后缀的公共长度并取出最大公共的前缀
代码：
/*给定出一个字符串，输出最长的重复子字符串*/
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int MaxCharNum = 5000000;
bool StrCmp(char* str1,char* str2);
void GenSuffixArray(char* str,char* suffixStr[]);
int ComStrLen(char* str1,char* str2);
void GenMaxReStr(char* str);
int main()
{
char str[MaxCharNum];
cin.getline(str,MaxCharNum);//遇到回车结束
GenMaxReStr(str);
system("pause");
return 1;
}
void GenMaxReStr(char* str)
{
int len = strlen(str);
int comReStrLen = 0;
int maxLoc = 0;
int maxLen = 0;
char* suffixStr[MaxCharNum];
GenSuffixArray(str,suffixStr);//产生后缀数组
//对后缀数组进行排序
sort(suffixStr,suffixStr+len,StrCmp);
//统计相邻单词中相同的字符数，并输出结果
for (int i = 0;i < len-1;i++ )
{
comReStrLen = ComStrLen(suffixStr[i],suffixStr[i+1]);
if (comReStrLen > maxLen)
{
maxLoc = i;
maxLen = comReStrLen;
}
}
//输出结果
for (int i = 0;i < maxLen;i++)
{
cout<<suffixStr[maxLoc][i];
}
cout<<endl;
}
/*为字符串产生其后缀数组，并存放到数组suffixStr中*/
void GenSuffixArray(char* str,char* suffixStr[])
{
int len = strlen(str);
for (int i = 0;i < len;i++)
{
suffixStr[i] = &str[i];
}
}
/*返回str1和str2的共同前缀的长度*/
int ComStrLen(char* str1,char* str2)
{
int comLen = 0;
while(*str1 && *str2)
{
if (*str1 == *str2)
{
comLen++;
}
str1++;
str2++;
}
return comLen;
}
//字符串升序排序
bool StrCmp(char* str1,char* str2)
{
if (strcmp(str1,str2) >=0 )
{
return false;
}
return true;
}