【已解决】如何用递归哈希算法或匹配表算法搜索字符串

思想之翼 · 发表于 2023-3-29 18:41:36

本帖最后由思想之翼于 2023-4-9 05:37 编辑

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 · 发表于 2023-3-29 19:04:40

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

感觉和这个有点相似？

xczxczxcz · 发表于 2023-3-29 19:47:25

是不是介样子呢？

$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 · 发表于 2023-4-1 22:45:29

@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;
}

复制代码

思想之翼 · 发表于 2023-4-7 23:24:32

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

terse · 发表于 2023-4-8 18:41:22

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

思想之翼 · 发表于 2023-4-8 20:27:26

本帖最后由思想之翼于 2023-4-8 21:34 编辑

回复 6# terse
您好！是的。

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

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

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

WHY · 发表于 2023-4-8 22:04:30

回复 5# 思想之翼

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

WHY · 发表于 2023-4-8 22:12:58

回复 7# 思想之翼

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

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

思想之翼 · 发表于 2023-4-8 22:40:39

本帖最后由思想之翼于 2023-4-8 22:57 编辑

回复 9# WHY

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

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

WHY · 发表于 2023-4-9 01:13:49

回复 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 · 发表于 2023-4-9 01:19:48

回复 10# 思想之翼

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

WHY · 发表于 2023-4-9 22:34:24

本帖最后由 WHY 于 2023-4-10 07:26 编辑

我贴一个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

复制代码

思想之翼 · 发表于 2023-4-9 23:32:19

回复 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 · 发表于 2023-4-10 00:15:59

回复 14# 思想之翼

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

		自动登录	找回密码
密码			注册

[新手上路]批处理新手入门导读	[视频教程]批处理基础视频教程	[视频教程]VBS基础视频教程	[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动	[批处理精品]CMD命令50条不能说的秘密	[在线下载]第三方命令行工具	[在线帮助]VBScript / JScript 在线参考

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

评分

评分

评分

评分

评分

评分

评分

评分

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

评分

评分

评分

评分

评分

评分

评分

评分

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