重新整理数据结构与算法(c#)——KMP破解[二十七]
2023-09-14 08:59:24 时间
前言
很多人把KMP和暴力破解分开,其实KMP就是暴力破解,整个高大上的名字,难道还不是去试错匹配吗?
KMP是这样子的,比如说:
绿色部分是我要匹配的。
按照一般写法是这样子的:
ABABA 去匹配 ABABC 发现匹配不了,然后后移一位用BABACDEFG 去匹配 ABABC。
KMP在此做了优化,本来后移一位的,这时候KMP后移两位再去匹配。
那么这个两位是怎么来的呢?
下面是规律:
正文
普通暴力破解:
static void Main(string[] args)
{
string str1 = "不玩德玛西亚之力这可真的不是太好!";
string str2 = "太好";
int index=violenceMatch(str1,str2);
Console.WriteLine(index);
Console.Read();
}
public static int violenceMatch(String str1, String str2)
{
int i = 0;
int j = 0;
while (i<str1.Length&&j<str2.Length)
{
if (str1[i] == str2[j])
{
i++;
j++;
}
else
{
i = i - (j - 1);
j = 0;
}
}
if (j == str2.Length)
{
return i - j;
}
return -1;
}
kmp 暴力破解:
static void Main(string[] args)
{
String str1 = "BBC ABCDAB ABCDABCDABDE";
String str2 = "ABCDABD";
int[] next = kmpNext("ABCDABD");
int index= kmpSearch(str1,str2,next);
Console.WriteLine(index);//15
Console.Read();
}
public static int kmpSearch(string str1, string str2, int[] next)
{
for (int i = 0, j = 0; i < str1.Length; i++)
{
while (j > 0 && str1[i] != str2[j])
{
j = next[j - 1];
}
if (str1[i] == str2[j])
{
j++;
}
if (j == str2.Length)
{
return i - j+1;
}
}
return -1;
}
public static int[] kmpNext(string dest)
{
int[] next = new int[dest.Length];
//如果只有一个那么没有前缀和后缀
next[0] = 0;
for (int i = 1,j=0; i < dest.Length; i++)
{
while (j>0&& dest[i] != dest[j])
{
j = next[j - 1];
}
if (dest[i] == dest[j])
{
j++;
}
next[i] = j;
}
return next;
}
相关文章
- C#数据结构与算法揭秘五
- C#中使用SHA1算法对密码进行加密
- 重新整理数据结构与算法(c#)——算法套路k克鲁斯算法[三十]
- 重新整理数据结构与算法(c#)—— 算法套路分治算法[二十五]
- 重新整理数据结构与算法(c#)—— 线索化二叉树[二十]
- C#设计模式——职责链模式(Chain Of Responsibility Pattern)
- C#实现所有经典排序算法
- 重新整理数据结构与算法(c#)——算法套路普利姆算法[二十九]
- C# 字符串中多个连续空格转为一个空格
- 浅析C#深拷贝与浅拷贝
- Atitit. 注册表操作查询 修改 api与工具总结 java c# php js python 病毒木马的原理
- Twitter的分布式自增ID算法snowflake(雪花算法) - C#版
- (33)C#模式匹配 ( pattern matching )
- (27)C#访问SQLite数据库
- C#多线程与异步
- C#常用的算法
- C#数据库编程(建立数据库表,数据库的连接,实现的源代码)