-
Notifications
You must be signed in to change notification settings - Fork 1
/
28strStr_KMP.cs
67 lines (59 loc) · 1.91 KB
/
28strStr_KMP.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace strStr_KMP
{
class Program
{
static void Main(string[] args)
{
}
/*
*
http://yyeclipse.blogspot.ca/2013/02/leetcode-implement-strstr-string.html
*/
public String strKMP(String haystack, String needle)
{
if (needle.Length == 0)
return haystack;
//get next array
int[] next = generateNext(needle.ToCharArray());
int len = 0; // Number of characters matched
for (int i = 0; i < haystack.Length; i++)
{
while (len > 0 && needle[len] != haystack[i])
len = next[len];
if (needle[len] == haystack[i])
len++;
if (len == needle.Length)
return haystack.Substring(i - needle.Length + 1);
}
return null;
}
/**
* KeyPoint. Get next array.
* @param needle
* @return
*/
private int[] generateNext(char[] needle)
{
// next array. next[i] means when match length = i,
// the common prefix and real suffix length = next[i]
int[] next = new int[needle.Length + 1];
//the longest common length of prefix and real suffix.
int presufix = 0;
//next[1] = 0, starting from 2. i = match length.
for (int i = 2; i < next.Length; i++)
{
while (presufix > 0 && needle[presufix] != needle[i - 1])//trickiest part
presufix = next[presufix];
if (needle[presufix] == needle[i - 1])
presufix++;
next[i] = presufix;
}
return next;
}
}
}