KMP algorithm challenge string.Contains

时间:2023-03-09 16:50:32
KMP algorithm challenge string.Contains

KMP:

 public int KMP (ReadOnlySpan<char> content, ReadOnlySpan<char> span) {
_next = new int[span.Length];
GetNext (span);
int i = 0;
int j = 0;
while (i < content.Length && j < span.Length) {
if (j == 0 || content[i] == span[j]) {
if(content[i]==span[j])
j++;
i++; } else
j = _next[j];
}
if (j >= span.Length)
return i - span.Length;
else
return -1; } private void GetNext (ReadOnlySpan<char> content) {
_next[0] = 0;
for (int i = 1; i < _next.Length; i++) {
if (_next[i - 1] != 0) {
if (content[i] == content[_next[i - 1]])
_next[i] = _next[i - 1] + 1;
} else {
if (content[0] == content[i])
_next[i] = 1;
else
_next[i] = 0;
}
}
}

string.Contains and KMP benchmarks:

  [Benchmark]
public void TestStringContain()
{
string s = "abcasdfasfdkjefasdfasdaaadfdfasdfasdfasdfjjsdjfjsglskdfjskdjfaskjdflkasjgksajdfksjdf";
bool x = s.Contains("asdfasd",StringComparison.Ordinal);
} [Benchmark]
public void TestKMP()
{
int x = containKeyWords.KMP("abcasdfasfdkjefasdfasdaaadfdfasdfasdfasdfjjsdjfjsglskdfjskdjfaskjdflkasjgksajdfksjdf", "asdfasd");
}

result:

KMP algorithm challenge string.Contains

Complete defeat!