本文共 1831 字，大约阅读时间需要 6 分钟。
题目：给定两个字符串，求两个字符串最长连续字符串的数目。比如：query为“acbac”，text为“acaccbabb”，那么最长的连续子序列为“cba”，输出3。请注意程序效率。
题目解析：
一开始看到这个题，可能会想到最长公共子序列的方法，其实是不对的。因为这里要求必须连续，而最长公共子序列为不连续的。状态转移方程不对。
方案一：暴力求法
可以分别将query的第0位到第n-1位为起始字符串，在text中遍历，寻找最长的子串。
时间复杂度较高O(m*n).
方案二：动态规划
这里很不容易想到动态规划，dp[i][j]这么和dp[i-1][j]/dp[i][j-1]/dp[i-1][j-1]寻找关系？不能随便删掉一个字符。
这里就需要思维的扩展了，当j+1时，dp[i][j+1] 和dp[i][j]什么关系呢？也就是j序列多了一个字符，要么不影响最大长度，dp[i][j+1] = dp[i][j]; 要么第j+1个字符结尾的长度变大。那么就需要以j+1结尾的字符，在0.....i之间遍历。找到最大长度。
根据这个思路，就能写出动态规划算法。
#includeusing namespace std;int TailLengh(string test,int pos1,string goal,int pos2){ int i = pos1,j = pos2,end = j; int mark,temp = 0; int max = 0; while(i>=0){ if(test[i] == goal[j]){ temp = 0; mark = i; while(i>=0 && j >=0 && test[i--] == goal[j--]) ++temp; if(j<0) return temp; if(temp > max) max = temp; i = mark; j = end; } --i; } return max;}int FindLongest(string test,string goal){ if(test.size() == 0 || goal.size() == 0) return 0; int len_t = test.size(); int len_g = goal.size(); int **dp = new int*[len_t+1]; for(int i =0;i <= len_t;i++) dp[i] = new int[len_g+1]; for(int i = 0;i <= len_t;i++) dp[i][0] = 0; for(int j = 0;j <= len_g;j++) dp[0][j] = 0; for(int i = 1;i <= len_t;i++){ for(int j = 1;j <= len_g;j++){ int temp = TailLengh(test,i-1,goal,j-1); dp[i][j] = temp > dp[i][j-1] ? temp : dp[i][j-1]; } } int res = dp[len_t][len_g]; for(int i = 0;i <= len_t;i++) delete []dp[i]; delete []dp; return res;}int main(){ string test = "sdfasdfadsffortqest"; string goal = "ccsdfasdfadsffortquery"; cout << FindLongest(test,goal) << endl; return 0;}
转载地址：http://alryb.baihongyu.com/