[文本处理] 【已解决】如何用 递归哈希算法 或 匹配表算法 搜索字符串

思想之翼

https://zhuanlan.zhihu.com/p/389419957
该文阐述字符串搜索算法有  朴素算法   Rabin-karp算法(递归哈希)   Kruth-Morris-Pratt算法(匹配表)，这三种算法，时空复杂度犹如云泥之别。
文章结论：由于在文本字符串中遍历时，不管模式字符串多长，每次计算量只涉及一次旧值的去除和一次新值的添加，Rabin Karp算法最适合用于模式字符串非常长的情况，比如长句子在论文中的查重。
我曾用VBS代码解决类似字符串匹配问题，运行速度之慢，难于言表。
限于网络难以搜寻到类似参考代码，故特举例，恳请各位老师指点(不拘泥于上述列举算法)。

例：文本A.txt 记录字符串
W
A
D
C
B
A
D
C
B
A

1.首先，读取A.txt文本字符串，并反转文本字符串为：ABCDABCDAW
2.其次，始终以A为起点，选择模式字符串。本例中，ABCDA 在文本字符串中存在2个及以上，且为最长相同字符串，故确定 ABCDA 为模式字符串。
3.然后，在文本字符串中，提取模式字符串的前缀。
4.结果：本例提取的前缀为D，写入文本B.txt  ；如有多个模式字符串的前缀，则不去重，依次竖排(另起一行)写入文本B.txt。

czjt1234

http://www.bathome.net/thread-65332-1-1.html

感觉和这个有点相似？

xczxczxcz

是不是介样子呢？

$t='WADCBADCBAFEGFLIFABCDEFABCDEFALI';
$f=$t.ToCharArray();
[array]::Reverse($f);
$e=-join($f);

$d=[regex]::Matches($e, "(?s)(.)((?:(?!\1).)+)\1(?=\2\1){1,}").value;

# 这是获取最长一个为 :输出B
if($null -ne $d -and $d.Length -gt 0){
	$s=[Linq.Enumerable]::Max($d, [func[object,int]]{param($i); $i.Length;});
	$d.Where{$_.Length -eq $s}.Foreach{$_.SubString($_.Length-2,1)}
}

# 这是获取每一个为 ;输出 B;D
if($null -ne $d -and $d.Length -gt 0){
	$d.ForEach{$_.SubString($_.Length-2,1)}
}
复制代码

WHY

@if(0)==(0) echo off
type a.txt | cscript //nologo //e:jscript "%~f0" > b.txt
pause & exit
@end

var str = WSH.StdIn.ReadAll().replace(/\s/g, '');
var Len = str.length;
var flag = false;

for (var i = Len-1; i > 0; i--) {
    var key = str.substr(Len-i);
    for (var j = 0; j < Len-i; j++) {
        if (str.substr(j, i) === key) {
            flag = true;
            WSH.Echo(str.substr(i+j, 1));
        }
    }
    if (flag) break;
}
复制代码

思想之翼

回复 4# WHY
感谢！有一点疑惑：计算1列2000行的数据，该代码耗时22秒，VBS代码却只耗时0.07125秒，老刘一号不是说：“随便换个编译型语言效率就可以薄纱vbs”吗？

terse

回复 5# 思想之翼
计算1列2000行 应该不需要22秒  一楼的意思应该是要匹配的字符总是第一位开始 是这样吗

思想之翼

回复 6# terse
您好！是的。

递增：A(有重复)  AB(有重复)  ABC(有重复)  ABCD(有重复) ABCDA(有重复)  ABCDAB(无重复)...  找到ABCDA有重复，且最长字符串。

从总字符串的一半(奇数则+1)开始递减，是否更快？
ABCDAB(无重复)   ABCDA(有重复)... 找到ABCDA有重复，且最长字符串。

实际运用中，没有极端情况，比如：AAAAAAAAAAAAAA 或者 ABABABABABABAB 或者 ABCABCABCABC ...

WHY

回复 5# 思想之翼


    把你测试用的 2000 行的文本放到网盘，分享链接，我看看是什么情况。

WHY

回复 7# 思想之翼


   

从总字符串的一半(奇数则+1)开始递减，是否更快？

这种办法行不通，WADCBADCBA，WADCBADCBA，出现重复的子串在整个字符串中是重叠的。
你不能确定被截掉的另一半是否有重复的子串。

思想之翼

回复 9# WHY

链接：https://pan.baidu.com/s/1Jw90mkqCSH1AzBsqvM_wfg?pwd=v5ak
提取码：v5ak

感谢帮助！您的代码这次测试是6.23秒，VBS代码测试是0.14秒

WHY

回复 10# 思想之翼

@if(0)==(0) echo off
type a.txt | cscript //nologo //e:jscript "%~f0" > b.txt
pause & exit
@end

var str = WSH.StdIn.ReadAll().replace(/\s/g, '');
var Len = str.length;

for (var i = Len-1; i > 0; i--) {
    var key = str.substr(Len-i);
    var arr = str.substr(0, Len-1).split(key);
    if (arr.length > 1) {
        for (var j = 0; j < Len-i; j++) {
            if (str.substr(j, i) === key) {
                WSH.Echo(str.substr(i+j, 1));
            }
        }
        break;
    }
}
复制代码

WHY

回复 10# 思想之翼


    这个VBS脚本不能用来解决这个问题，思路不一样。
如果字符串是：WADCBADCBAADCBA
应该提取红色的两个字符D和A，VBS只提取了一个A

WHY

我贴一个vbs，0.03s 左右

ST = Timer

Dim srcFile, dstFile
srcFile = "a.txt"
dstFile = "b.txt"

Dim fso, objFile
Set fso = CreateObject("Scripting.FileSystemObject")
Set objFile = fso.OpenTextFile(srcFile, 1)

Dim strIn, strLine
strIn = ""
Do Until objFile.AtEndOfStream
   strLine = objFile.ReadLine
   If strLine <> "" Then strIn =  strLine & strIn
Loop

Dim reg
Set reg = New RegExp
reg.Global = True

Dim strOut, i, key, match
strOut = ""
For i = Len(strIn)-1 To 1 Step -1
    key = Left(strIn, i)
    If InStr(2, strIn, key) > 0 Then
        reg.Pattern = ".(?=" & key & ")"
        For Each match In reg.Execute(strIn)
            strOut = strOut & match & vbCrLf
        Next
        Exit For
    End If
Next

fso.OpenTextFile(dstFile, 2, True).Write(strOut)

MsgBox Timer - ST
复制代码

思想之翼

回复 11# WHY
虚心请教：下述表示路径出错，如何正确表述？
type a.txt | cscript //nologo //e:jscript "%~f0" > b.txt
type d:\测试1\a.txt | cscript //nologo //e:jscript "%~f0" > e:\测试2\b.txt

WHY

回复 14# 思想之翼


    报错信息是什么？
D:\测试1\a.txt 和 E:\测试2 必须是真实存在的。脚本必须 ANSI 编码，UTF8 编码的话中文会出现乱码。