写一个函数,返回两个字符串的最大公因子串? 写一个函数,返回两个字符串的最大公因子串?今天的笔试题,求解!语言不限 解决方案 » 免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货 获取相同部分var c=a.ToCharArray().Intersect(b.ToCharArray()).ToArray(); 2楼方法有问题,它的作用是找出两个集合中都出现的元素,这样就不能保证是连续的应该不是楼主想要的法楼主还是自己配合String.Indexof循环比较吧,正则我不会代码我懒的写 string a = "acef"; string b = "abcd"; string str = ""; private void button1_Click(object sender, EventArgs e) { foreach (char i in a.ToCharArray()) { foreach (char j in b.ToCharArray()) { if (i == j) { str += i; } } } MessageBox.Show(str.ToString()); } 不要弄这么深奥,直接告诉别人两个字串,请找出其最长的相同连续字串... ...例如AABBCCCDDDDAAABBCCDDDD最大公因字串:CCDDDD 今天了解到,原来这个是个LCS算法,贴出来给大家分享下:LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1序列,其对应的位置就是最长匹配子串的位置。下面是字符串21232523311324和字符串312123223445的匹配矩阵,前者为X方向的,后者为Y方向的。不难找到,红色部分是最长的匹配子串。通过查找位置我们得到最长的匹配子串为:212320 0 0 1 0 0 0 1 1 0 0 1 0 0 00 1 0 0 0 0 0 0 0 1 1 0 0 0 01 0 1 0 1 0 1 0 0 0 0 0 1 0 00 1 0 0 0 0 0 0 0 1 1 0 0 0 01 0 1 0 1 0 1 0 0 0 0 0 1 0 00 0 0 1 0 0 0 1 1 0 0 1 0 0 01 0 1 0 1 0 1 0 0 0 0 0 1 0 01 0 1 0 1 0 1 0 0 0 0 0 1 0 00 0 0 1 0 0 0 1 1 0 0 1 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 1 00 0 0 0 0 0 0 0 0 0 0 0 0 1 00 0 0 0 0 1 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0但是在0和1的矩阵中找最长的1对角线序列又要花去一定的时间。通过改进矩阵的生成方式和设置标记变量,可以省去这部分时间。下面是新的矩阵生成方式:0 0 0 1 0 0 0 1 1 0 0 1 0 0 00 1 0 0 0 0 0 0 0 2 1 0 0 0 01 0 2 0 1 0 1 0 0 0 0 0 1 0 00 2 0 0 0 0 0 0 0 1 1 0 0 0 01 0 3 0 1 0 1 0 0 0 0 0 1 0 00 0 0 4 0 0 0 2 1 0 0 1 0 0 01 0 1 0 5 0 1 0 0 0 0 0 2 0 01 0 1 0 1 0 1 0 0 0 0 0 1 0 00 0 0 2 0 0 0 2 1 0 0 1 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 1 00 0 0 0 0 0 0 0 0 0 0 0 0 1 00 0 0 0 0 1 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0不用多说,你大概已经看出来了。当字符匹配的时候,我们并不是简单的给相应元素赋上1,而是赋上其左上角元素的值加一。我们用两个标记变量来标记矩阵中值最大的元素的位置,在矩阵生成的过程中来判断当前生成的元素的值是不是最大的,据此来改变标记变量的值,那么到矩阵完成的时候,最长匹配子串的位置和长度就已经出来了。这样做速度比较快,但是花的空间太多。我们注意到在改进的矩阵生成方式当中,每生成一行,前面的那一行就已经没有用了。因此我们只需使用一维数组即可。最终的代码如下: Private Function LCS(ByVal str_1 As String, ByVal str_2 As String) As String If str_1 = "" Or str_2 = "" Then Return "" Dim c(str_1.Length) As Integer Dim max, maxj, i, j As Integer maxj = 0 : max = 0 '这两个是标志变量 For i = 0 To str_2.Length - 1 For j = str_1.Length - 1 To 0 Step -1 If str_2.Chars(i) = str_1.Chars(j) Then If i = 0 Or j = 0 Then c(j) = 1 Else c(j) = c(j - 1) + 1 End If Else c(j) = 0 End If If c(j) > max Then '把>改成>=则返回最后一个最长匹配子串 max = c(j) : maxj = j '更新标志变量 End If Next Next If max = 0 Then Return "" Return str_1.Substring(maxj - max + 1, max) '直接从标志变量得出结果 End Function这里的问题大概你也看出来了:如果有多个最长的匹配子串怎么办呢?我这里只能是返回第一个。稍微改一下可以变成返回最后一个。要完整地返回所有最长匹配子串,就需要一个标志变量的数组了。你有兴趣改改吗? 请教客户端调用webservice的问题 判断坐标点是否在圆内 C#如何获得当前窗体正处于输入状态的控件 3des加密问题了的进来看看TripleDESCryptoServiceProvider 关于httpwebrequest 如何把汉字(简体中文)转换成GBK编号的格式 form2继承自form1,如何让form2能再加上其他的控件呀? netCHARTING 的每条柱的宽度怎么调整 上传方法 急 请问RegularExpressionValidator怎么判为控件不为空并为Email地址 ld2文件如何用c# 读取 在c#中怎样建立文件夹
var c=a.ToCharArray().Intersect(b.ToCharArray()).ToArray();
这样就不能保证是连续的
应该不是楼主想要的法楼主还是自己配合String.Indexof循环比较吧,正则我不会
代码我懒的写
string b = "abcd";
string str = ""; private void button1_Click(object sender, EventArgs e)
{
foreach (char i in a.ToCharArray())
{
foreach (char j in b.ToCharArray())
{
if (i == j)
{ str += i;
}
}
}
MessageBox.Show(str.ToString());
}
两个字串,请找出其最长的相同连续字串... ...
例如
AABBCCCDDDD
AAABBCCDDDD
最大公因字串:CCDDDD
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
但是在0和1的矩阵中找最长的1对角线序列又要花去一定的时间。通过改进矩阵的生成方式和设置标记变量,可以省去这部分时间。下面是新的矩阵生成方式:
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0 2 1 0 0 0 0
1 0 2 0 1 0 1 0 0 0 0 0 1 0 0
0 2 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 3 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 4 0 0 0 2 1 0 0 1 0 0 0
1 0 1 0 5 0 1 0 0 0 0 0 2 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 2 0 0 0 2 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
不用多说,你大概已经看出来了。当字符匹配的时候,我们并不是简单的给相应元素赋上1,而是赋上其左上角元素的值加一。我们用两个标记变量来标记矩阵中值最大的元素的位置,在矩阵生成的过程中来判断当前生成的元素的值是不是最大的,据此来改变标记变量的值,那么到矩阵完成的时候,最长匹配子串的位置和长度就已经出来了。这样做速度比较快,但是花的空间太多。我们注意到在改进的矩阵生成方式当中,每生成一行,前面的那一行就已经没有用了。因此我们只需使用一维数组即可。最终的代码如下: Private Function LCS(ByVal str_1 As String, ByVal str_2 As String) As String
If str_1 = "" Or str_2 = "" Then Return "" Dim c(str_1.Length) As Integer
Dim max, maxj, i, j As Integer
maxj = 0 : max = 0 '这两个是标志变量
For i = 0 To str_2.Length - 1
For j = str_1.Length - 1 To 0 Step -1
If str_2.Chars(i) = str_1.Chars(j) Then
If i = 0 Or j = 0 Then
c(j) = 1
Else
c(j) = c(j - 1) + 1
End If
Else
c(j) = 0
End If
If c(j) > max Then '把>改成>=则返回最后一个最长匹配子串
max = c(j) : maxj = j '更新标志变量
End If
Next
Next If max = 0 Then Return ""
Return str_1.Substring(maxj - max + 1, max) '直接从标志变量得出结果
End Function
这里的问题大概你也看出来了:如果有多个最长的匹配子串怎么办呢?我这里只能是返回第一个。稍微改一下可以变成返回最后一个。要完整地返回所有最长匹配子串,就需要一个标志变量的数组了。你有兴趣改改吗?