admin管理员组文章数量:1636900
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1
if needle is not part of haystack.
实现strStr()。
找到字符串的子串位置,并返回。如果没有则返回-1
程序:
public class ImplementStrStr
{
//原生字符串匹配算法
public static int StrStrNaive(string haystack, string needle)
{
if (needle.Length == 0)
return 0;
for (int i = 0; i < haystack.Length - needle.Length + 1; i++)
{
if (haystack[i] == needle[0])
{
bool equal = true;
for (int j = 0; j < needle.Length; j++)
{
if (needle[j] != haystack[i + j])
{
equal = false;
break;
}
}
if (equal == true) return i;
}
}
return -1;
}
//Rabin-Karp 算法
public static int StrStrRabinKarp(string haystack, string needle)
{
int len = needle.Length;
//两个特殊的用例
if (haystack.Length < len)
{
return -1;
}
if (needle == "")
{
return 0;
}
//用于rabin-karp哈希函数的基本素数
int basement = 256;
//用于缩小哈希值的素数
int prime = 31;
//用于与要从哈希中删除的字符相乘的因子
int factor = (int)((Math.Pow(basement, needle.Length - 1)) % prime);
//得到指针和初始窗口的ascii值
int needleHash = 0;
int windowHash = 0;
byte[] needleBytes = Encoding.ASCII.GetBytes(needle);
byte[] windowBytes = Encoding.ASCII.GetBytes(haystack.Substring(0, len));
//为两者生成哈希值
for (int i = 0; i < needle.Length; i++)
{
needleHash = (needleHash * basement + needleBytes[i]) % prime;
windowHash = (windowHash * basement + windowBytes[i]) % prime;
}
//循环找到匹配
bool findMatch = true;
for (int i = 0; i < haystack.Length - len + 1; i++)
{
//如果哈希值匹配,以防哈希值不唯一,则遍历针和窗口
if (needleHash == windowHash)
{
findMatch = true;
for (int j = 0; j < len; j++)
{
if (needle[j] != haystack[i + j])
{
findMatch = false;
break;
}
}
if (findMatch == true) return i;
}
//移动滑动窗口并找到新窗口的哈希值
if (i < haystack.Length - len)
{
byte removeByte = Encoding.ASCII.GetBytes(haystack.Substring(i, 1))[0];
byte addByte = Encoding.ASCII.GetBytes(haystack.Substring(i + len, 1))[0];
//rolling hash的函数
windowHash = ((windowHash - removeByte * factor) * basement + addByte) % prime;
//ensure the window hash to be positive
if (windowHash < 0)
{
windowHash += prime;
}
}
}
return -1;
}
}
单元测试(通过):
[TestClass]
public class UnitTest28_ImplementStrStr
{
[TestMethod]
public void TestMethodStrStrNaive()
{
string haystack = "This is an interesting problem.";
string needle1 = "";
string needle2 = " int";
string needle3 = "probleem";
Assert.AreEqual(0, ImplementStrStr.StrStrNaive(haystack, needle1));
Assert.AreEqual(10, ImplementStrStr.StrStrNaive(haystack, needle2));
Assert.AreEqual(-1, ImplementStrStr.StrStrNaive(haystack, needle3));
}
[TestMethod]
public void TestMethodStrStrRabinKarp()
{
string haystack = "abc def";
string needle = "abc";
Assert.AreEqual(0, ImplementStrStr.StrStrRabinKarp(haystack, needle));
haystack = "abcdef";
needle = "cd";
Assert.AreEqual(2, ImplementStrStr.StrStrRabinKarp(haystack, needle));
haystack = "abcd";
needle = "";
Assert.AreEqual(0, ImplementStrStr.StrStrRabinKarp(haystack, needle));
haystack = "ab";
needle = "abc";
Assert.AreEqual(-1, ImplementStrStr.StrStrRabinKarp(haystack, needle));
haystack = "abcd efg";
needle = "hij";
Assert.AreEqual(-1, ImplementStrStr.StrStrRabinKarp(haystack, needle));
//leetcode test case 65/72 I did not pass in the first time
haystack = "aaaabaaabbabbaaaaaabbabbbaaabababaaaaabbbbbbbbbbbbbbbaabbbbabbaababbbababababaaaabbbbaaabababbbaaabbaabbabbbbbababbabbaabbbabaabaaaaabbbaaaaaabaaaabababababbaabaabbaaaaaaaababbabaa";
needle = "aabbaaaabbbbaabaaabaabbaaababbabbbbbaba";
//Assert.AreEqual(-1, ImplementStrStr.StrStrRabinKarp(haystack, needle));
haystack = "baabbaaaaaaabbaaaaabbabbababaabbabbbbbabbabbbbbbabababaabbbbbaaabbbbabaababababbbaabbbbaaabbaababbbaabaabbabbaaaabababaaabbabbababbabbaaabbbbabbbbabbabbaabbbaa";
needle = "bbaaaababa";
Assert.AreEqual(107, ImplementStrStr.StrStrRabinKarp(haystack, needle));
}
}
版权声明:本文标题:28.Implement strStr() 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1729234177a1191801.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论