山寨机中的战斗机！	程序优化工程师到底对IT界有没有贡献

高分求字符串比较的算法

楼主wdtclv（将军）2005-11-11 15:06:02 在 .NET技术 / ASP.NET 提问

已知字符串1 = “12345678”
字符串2 = “122346588”
要求：
1、将两个字符串的不同比较出来（假设字符串1是正确的）
2、将字符串2中错误的地方标识出来
问题点数：100、回复次数：57Top

1 楼Macosx（结贴）回复于 2005-11-11 15:08:58 得分 1

还有其它的要求没就这两个要求很模糊啊Top

2 楼wdtclv（将军）回复于 2005-11-11 15:11:07 得分 0

就像beyond compare 那样，能够比较两个文件的差异，
这里我只想实现比较两个字符串的差异Top

3 楼wdtclv（将军）回复于 2005-11-11 15:21:16 得分 0

没有人会吗？Top

4 楼eightdou（）回复于 2005-11-11 15:23:27 得分 1

不知道别的方法，原始方法就是一个字符一个字符的比较
有不一样的地方就是出错的地方了Top

5 楼wdtclv（将军）回复于 2005-11-11 15:29:27 得分 0

楼上的说法似乎是行不通的，如果两个字符串的长度不一样就不行了（不如多了些同样的字符或漏掉了某些字符）Top

6 楼lovebaby999（小公司的程序员）回复于 2005-11-11 15:44:27 得分 1

感觉你的要求说的不明确啊
Top

7 楼wdtclv（将军）回复于 2005-11-11 15:51:48 得分 0

简单的说就是象打字练习那样
给定一段文字，练习者对照着输入，完成后在对原稿和练习者输入的稿子进行校对。
把打错的地方标识出来
这回能明白吗Top

8 楼sunnystar365（一个人的天空）回复于 2005-11-11 16:03:17 得分 1

打字练习也是一个一个比较的啊。
可以对这两个字符串先进行长度比较。如果长度不相等就表示两者不同。
否则每个字符串截取同一个位置的字符，进行比较，当然要记住前一个截取的
位置是在什么地方，进行单个字符的比较。
只是一些意见，实现起来可能有些麻烦。Top

9 楼wdtclv（将军）回复于 2005-11-11 16:07:11 得分 0

是比较麻烦阿，所以才想问问大家有什么高见阿Top

10 楼wdtclv（将军）回复于 2005-11-11 16:08:16 得分 0

可以对这两个字符串先进行长度比较。如果长度不相等就表示两者不同。
即便是长度相等内容也有可能不同啊！Top

11 楼wdtclv（将军）回复于 2005-11-14 09:05:32 得分 0

没人遇到过这种问题吗Top

12 楼natumi（夏実）回复于 2005-11-14 09:09:46 得分 1

用循环来截取每一位进行比较不行吗Top

13 楼wdtclv（将军）回复于 2005-11-14 09:29:13 得分 0

楼上的肯定不行
按位截的话多打或漏打得情况就没法比较了
Top

14 楼zhanqiangz（闲云野鹤－Overriding）回复于 2005-11-14 09:48:55 得分 2

转化为char数据，用相同索引的元素对应比较。Top

15 楼zhanqiangz（闲云野鹤－Overriding）回复于 2005-11-14 09:49:23 得分 0

转化为char数组，不是数据。）：Top

16 楼wdtclv（将军）回复于 2005-11-14 09:53:06 得分 0

楼上的大哥具体点
Top

17 楼cjzlxy（享受孤独）回复于 2005-11-14 10:03:11 得分 5

for(int i=0;i<字符串1.Lentgh;i++)
{
Char c= 字符串1[i];
for(int j =0;j<字符串2;j++)
{
//比较字符串1[i]和字符串2[j];
if(字符串[i]==字符串2[j])
...
else
...
}

}Top

18 楼wdtclv（将军）回复于 2005-11-14 10:14:03 得分 0

楼上的仁兄好像方法不行啊Top

19 楼jxzhang615（冰河）回复于 2005-11-14 10:23:56 得分 10

Private Function comparestring()
Dim string1 As String = "12345678"
Dim string2 As String = "12234658"
Dim i As Integer
If string1.Length <> string2.Length Then
MsgBox("两个字符串不同")
Else
For i = 1 To string1.Length
If Mid(string1, i, 1) <> Mid(string2, i, 1) Then
MsgBox("第" & i & "个字符不同")
End If
Next
End IfTop

20 楼jianjian54（键键）回复于 2005-11-14 10:58:48 得分 10

21 楼wdtclv（将军）回复于 2005-11-14 11:14:52 得分 0

1234567
12<font color = red>2</FONT>34<font color = red>65</FONT>7Top

22 楼wdtclv（将军）回复于 2005-11-14 11:17:43 得分 0

strA:1234567
strB:12234657
strB中实际出错的字符是2，6和5（相对于strA）
怎么找出来呢？Top

23 楼wdtclv（将军）回复于 2005-11-14 13:24:20 得分 0

继续顶起来Top

24 楼cw888（）回复于 2005-11-14 14:11:05 得分 5

数据结构：Point
public struct Point
{
public int x;
public char c;
}
比较子窜函数：
string s1 = "12345678";
string s2 = "21349671";
int s1Length = s1.Length;
ArrayList ret = new ArrayList();
if(s1Length == s2.Length)
{
for(int i=0; i<s1Length; i++)
{
if(s1[i] != s2[i])
{
Point st = new Point();
st.x = i;
st.c = s1[i];
ret.Add(st);
}
}
}
else
{
Console.WriteLine("The two string is not equal!");
}
for(int k=0; k<ret.Count; k++)
{

Point st = (Point)ret[k];
Console.WriteLine("The pos is: {0}={1}", st.x, st.c);
}Top

25 楼silentcross（中间件）回复于 2005-11-14 15:25:39 得分 5

我的一点想法，不知道有用没

从标准字符串里面逐个提取字符，到待验证的字符串里面查找，结果可分为两种：有和没有
比较字符是否相等，如果相等就为有
如果不相等，在待验证字符串中查找第一个相等的字符，比较着两个字符后面的几个（比如10）字符的匹配率，高于希望的值（如70%）为有

关于字符串匹配率我也没想清楚，但至少问题规模降下来了
关注中，希望看到高手解决之道Top

26 楼jianjian54（键键）回复于 2005-11-14 19:42:34 得分 0

你问的问题不明确有几种情况我下边说的 s 是对的 ss是错的
比如 1. s=123456 ss=133456 错悟的是第2个
2.s=123456 ss=1233456 错误的是第3个
3.s=123456 ss=12456 错误的第3个
4.s=123456 ss=12333456 错误的是第3个和第4个
我只是随便说了几种我想问下你的我问题究竟是什么情况
Top

27 楼wdtclv（将军）回复于 2005-11-16 09:34:37 得分 0

楼上的仁兄我的问题很简单，就是一个类似文稿的校对工作，就像报纸杂志的编辑校稿那样，拿原稿和打的稿件比较，只不过是通过程序去实现他，还是期望CSDN的牛人给出出主意啊Top

28 楼jianjian54（键键）回复于 2005-11-16 10:11:32 得分 0

这样考虑的问题太多了能力有限关注中Top

29 楼jianjian54（键键）回复于 2005-11-16 10:22:08 得分 0

问题出现的情况太多了我自己多搞不懂有多少中情况没有办法帮你在下无能为力 sorryTop

30 楼cm8983（思远）回复于 2005-11-16 10:29:46 得分 1

markTop

31 楼wang790809（石头）回复于 2005-11-16 10:38:35 得分 1

能力有限关注中Top

32 楼wdtclv（将军）回复于 2005-11-16 10:40:04 得分 0

坛子里带星的各位大侠帮着出出吧Top

33 楼wdtclv（将军）回复于 2005-11-16 10:40:29 得分 0

哪怕是给个思路也好啊Top

34 楼lijinjing（李进京）回复于 2005-11-16 11:01:05 得分 1

l=str1.length;
m=str2.length;
if(l<m)
{
从str2中抽取l个字符与str1进行比较;(遍历)
}
再递归Top

35 楼Liu_Qiang（人为财死，鸟为食亡）回复于 2005-11-16 11:40:20 得分 5

string str1 = "abcdefg";
string str2 = "abcdegf";

ArrayList al = new ArrayList();
if(str1.Length == str2.Length)
{
for(int i=0;i<str1.Length;i++)
{
if(str1[i] == str2[i])
{
al.Add(str1[i].ToString());
}
}
}
输出al的结果为：abcdeTop

36 楼wdtclv（将军）回复于 2005-11-16 13:24:12 得分 0

楼上的各位好像仅仅考虑到了一种或几种情况阿，有没有一个比较全面的算法阿Top

37 楼shoutor（www.mouxiao.com）回复于 2005-11-16 13:26:29 得分 1

分成数组，然后比较数组Top

38 楼rubygmm（itren）回复于 2005-11-16 13:34:02 得分 1

多数用数组Top

39 楼anheizhizi（目标:★★★★★）回复于 2005-11-16 13:55:03 得分 2

你的意思是不是： S1=123456，S2=12334556；
如果S1正确，标示出S2出错的放。 1233（错误）455（错误）6 这样？（字可以用颜色代替）
如果是这样，只要用循环比较2个字符串相同位的字符，如果不同，把不同的那个字符串的索引加一不就行了Top

40 楼anheizhizi（目标:★★★★★）回复于 2005-11-16 13:57:19 得分 0

上面说错了，不好意思。。。。

是先比较2个字符串是否相同，不同，就递归比较。Top

41 楼sonymusic（废除）回复于 2005-11-16 13:58:12 得分 40

粗略写一下我的想法

将两个string都转换为char()
char a() 原始数据
char b() 新数据
然后再用一个数组d()来记录b的每一个字符对应在a中的位置（比如不存在的用位置-1来表示），注意比较指针的移动控制。最后的这个数组如果d(i+1)=d(i)+1那么都算是正确的部分。剩余的部分都是出错的地方。

不知道说得清楚没有，具体过程不再详细贴上。
Top

42 楼yydy（一条活鱼）回复于 2005-11-16 14:02:43 得分 1

听讲Top

43 楼wdtclv（将军）回复于 2005-11-16 16:05:58 得分 0

to：anheizhizi
如果S1=123456，S2=1233465
用递归可能就不行了阿Top

44 楼wdtclv（将军）回复于 2005-11-16 16:08:51 得分 0

如果S1=123456，S2=12456
也不行啊Top

45 楼wdtclv（将军）回复于 2005-11-16 16:12:37 得分 0

to： sonymusic
你的想法我也试过，如果两个字符串的长度相等还可以，但是如果两个字符串长度不相等的话数组d()中记录的位置就会出现偏差了Top

46 楼syf2000119（ff）回复于 2005-11-16 16:13:55 得分 1

用数组Top

47 楼wdtclv（将军）回复于 2005-11-16 16:26:29 得分 0

to： syf2000119(ff)
怎么用？Top

48 楼sonymusic（废除）回复于 2005-11-16 17:19:58 得分 0

to: wdtclv(将军)
我就是考虑了位置偏差，结果并不时要求位置对。而是顺序对……

请看这个结果判断:
最后的这个数组如果d(i+1)=d(i)+1那么都算是正确的部分。剩余的部分都是出错的地方。
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

eg:
a="ABCDEFG"
b="AAAAACDFG"
D=0,-1,-1,-1,-1,2,3,4,5

a="ABCDEFG"
b="BCDGFA"
D=1,2,3,6,5,-1

a="AABCDAEFG"
b="BCEAEFG"
D=2,3,-1,5,6,7,8

到这样的结果的时候,我想你的目的应该可以达到了.:)
Top

49 楼sonymusic（废除）回复于 2005-11-16 23:53:20 得分 0

修正一下上面的结果：
a="ABCDEFG"
b="AAAAACDFG"
D=0,0,0,0,0,2,3,4,5

之前对重复字符没有专门处理，判断的时候需要增加这部分的判断。Top

50 楼wdtclv（将军）回复于 2005-11-17 09:54:57 得分 0

to ：sonymusic 老兄
如果按照：
最后的这个数组如果d(i+1)=d(i)+1那么都算是正确的部分。剩余的部分都是出错的地方。
那像
a="ABCDEFG"
b="AAAAACDFG"
D=0,0,0,0,0,2,3,4,5
这种情况第一位就会标示错了
Top

51 楼xu770（我爱鱼儿）回复于 2005-11-17 10:11:21 得分 1

Ultra CompareTop

52 楼wdtclv（将军）回复于 2005-11-17 11:18:08 得分 0

UE 是可以，我只是想要自己做啊Top

53 楼sonymusic（废除）回复于 2005-11-17 11:23:22 得分 0

to:wdtclv

a="ABCDEFG"
b="AAAAACDFG"
D=0,0,0,0,0,2,3,4,5

其实像这样的例子正好可以说明，这种情况第一位是否算错，你完全可以自己设定一个标准。因为这样的字串比对其实是模糊的判断了。好比就算人来判断，你也可以说错了，也可以说对了。因为字符个体是独立的，不联系上下文是无法判断的。当然第一个也比较特殊，完全可以根据位置来决定是否正确，如果这样判断的话，第一位是正确的，那后面的使用d(i+1)=d(i)+1来判断就都符合要求了。Top

54 楼hainang1234（海浪）回复于 2005-11-17 11:26:50 得分 3

static void Main()
{
string str1 = "123456789";
string str2 = "qq12345abc6789";
ArrayList list = com2(str1,str2);
foreach (object obj in list)
{
object[] arrayObj = (object[])obj;
strall += arrayObj[0].ToString()+"开始的"+arrayObj[1].ToString()+"位"+arrayObj[2].ToString()+"\r\n";
}
MessageBox.Show(strall);
}

static private ArrayList com2(string strold,string str2)
{
ArrayList putoutList = new ArrayList();
for (int j=0; j<str2.Length; j++)
{
for (int i=str2.Length-j; i>0; i--)
{
int re = strold.IndexOf(str2.Substring(j,i));
if (re != -1)
{
putoutList.Add(new object[]{j+1,i,"相等"});
j = j+i-1;
goto continueout;
}
}
//不相等
putoutList.Add(new object[]{j+1,1,"不相等"});

continueout:
continue;
}

return putoutList;
}Top

55 楼wdtclv（将军）回复于 2005-11-17 13:45:59 得分 0

to： sonymusic老兄
同样字符串的最后一位也不能比较
感谢你给的算法
看来也只能比较模糊的进行比较了Top

56 楼hainang1234（海浪）回复于 2005-11-17 15:28:19 得分 0

没试试我的？Top

57 楼fanshow（灵山霄）回复于 2005-11-18 12:10:21 得分 0

string strFir = "2345678";
string strSec = "223456778";
if (strFir == strSec)
{
System.Console.WriteLine("二者相等{0}:",strFir);
}
else
{

for (int s = 0; s < strSec.Length; ++s)
{
if (strFir.IndexOf(strSec[s]) == -1)
{//不包含
System.Console.WriteLine("不包含!!!!");
}

else if (strFir.IndexOf(strSec[s]) != strFir.LastIndexOf(strSec[s]))
{ //包含超过1次
System.Console.WriteLine("包含超过1次!!");
}

}
for (int s = 0; s < strSec.Length-1; ++s)
{
if (strFir.IndexOf(strSec[s]) == strFir.LastIndexOf(strSec[s + 1]))
{
System.Console.WriteLine("重复！！！");
}
}
}Top