求个字符串比较算法

Question

google kmp lcs algorithm

Answer 1

逐个遍历是不可避免的。即使是调用其他控件或函数，后台还是要遍历的。加快的窍门在于不要对原字符串作改动，例如在循环中删除非数字的字符，也不要通过增补结果字符串的方法来得到新字符串。因为长字符串的空间重新分配是耗时较多的，最好避免重复的字符串操作。Dim bResult() As Byte, sSource As String, i As Long, n As Long
Dim sResult As StringsSource = "A0012B2C56DE34H"
ReDim bResult(Len(sSource) - 1)
For i = 1 To Len(sSource)
    If Mid(sSource, i, 1) <= "9" Then
        n = n + 1
        bResult(n - 1) = Asc(Mid(sSource, i, 1))
    ElseIf i > 1 Then
        If Mid(sSource, i - 1, 1) <= "9" Then
            n = n + 1
            bResult(n - 1) = 32
        End If
    End If
Next i
ReDim Preserve bResult(n - 1)
sResult = StrConv(bResult, vbUnicode)MsgBox sResult

Answer 2

这种问题应当在插入时解决，而不是解析时。可以有多种协议来处理这类情况。比如插入的字符可能已经存在，可以先插入一个前导的非键盘输入字符，例如 0xFF，然后再插入实意字符。

Answer 3

我想到用分块来比较应该比较快一点，分块长度考虑取S1的1/10吧，没测试不知道效果，只是想法。
假设:
原串:S1="ABCDEFGHIJKLMNOPQRST"
新串:S2="A01BB235CDE589F695GH785I345J1312KLMN9897OOPQ898R234S34STT"
新串中红色部分为插入与原串中相同的字符
分块比较是：S1,S2从左边开始每次都截相同长度进行比较,载取长度定义为L变量,中间字符串定义为变量S3，初值S3=S2
如果S1L=S2L就不处理 '// 分块的目的就是这步可以节省一点时间
如果S1L<>S2L，逐个比较找出不相同的字符存入动态数组Z()，然后把S2L中不相同字符替换为空赋值给变量T=replace(S2L,Z(n),"") ,S3=replace(S3,S2L,T) 
如果S3=S1结束 
如果S3<>S1循环从下一个位置开始截取比较。分块应该是有效率的吧，假设
S1长度1000
S2长度1001
只要找到一次不相同的程序就结束了，不必一一比较
我想红色部分应该也能正确找出