c : 返回两个字符串的最长公共字符串 -凯发ag旗舰厅登录网址下载

 

原理: x 轴和 y 轴分别取 自身和 str2 然后表格对齐，

相同的字符 设成 1 其他为 0 ,取斜对角线 最长不为 0的字符串极为公共子字符串 

例如asbbefg 和 aubeg 最大值2

	a	s	b	b	e	f	g
a	1	0	0	0	0	0	0
u	0	0	0	0	0	0	0
b	0	0	1	1	0	0	0
e	0	0	0	0	1	0	0
g	0	0	0	0	0	0	1

由此可以看出，最长非0的斜对角线对应的单元格为 "be"所以 "be"是最长公共子字符串。

可以对算法进行优化：

在对表格进行赋值时，如果str1[i]==str2[j];   comparetbl[i] [j] = comparetbl[i-1] [j-1] 1 

	a	s	b	b	e	f	g
a	1	0	0	0	0	0	0
u	0	0	0	0	0	0	0
b	0	0	1	1	0	0	0
e	0	0	0	0	2	0	0
g	0	0	0	0	0	0	1

 

inline sstring sstring::maxcommonsubstr(sstring &str2) {//原理: 动态规划 x 轴和 y 轴分别取 自身和str2//然后表格对齐，相同的字符 设成 1 其他为 0 ,取斜对角线最长不为0//asbbefg 和 aubeg 最大值2/*a s b b e f ga 1 0 0 0 0 0 0u 0 0 0 0 0 0 0b 0 0 1 1 0 0 0e 0 0 0 0 2 0 0g 0 0 0 0 0 0 1*/int len1 = this->length();int len2 = str2.length();if (len1 ==0 || len2 == 0 ){return sstring();}int maxlen=-1; //最大长度int lastindex =-1; //最大值在主串的位置int comparetbl[len2][len1];for (int i = 0; i substring(lastindex-maxlen 1,maxlen);return ret;}

 

总结

以上是凯发ag旗舰厅登录网址下载为你收集整理的c : 返回两个字符串的最长公共字符串的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得凯发ag旗舰厅登录网址下载网站内容还不错，欢迎将凯发ag旗舰厅登录网址下载推荐给好友。