-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathKMP.java
More file actions
119 lines (101 loc) · 2.37 KB
/
Copy pathKMP.java
File metadata and controls
119 lines (101 loc) · 2.37 KB
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
package Kmp;
import org.junit.Test;
/**
* @author dekai.kong
* @difficult Hard
* @create 2020-07-26 13:08
* @from kmp https://www.zhihu.com/question/21923021
**/
public class KMP {
public KMP() {
}
public String kmp(String s1,String s2){
int[] next = getNext(s2);
int start = 0;
int i = 0;
int j = 0;
while (i < s1.length() && j < s2.length())
{
if (j == -1 || s1.charAt(i) == s2.charAt(j))
{
i++;
j++;
}
else {
j = next[j];
}
}
if (j == s2.length()){
start = i - j;
}
else {
start = -1;
}
return s1.substring(start,start+s2.length());
}
public int[] getNext(String bs){
int[] next = new int[bs.length()];
next[0] = -1;
for (int i=1;i<bs.length();i++)
{
int j=next[i-1];
while (bs.charAt(j+1)!=bs.charAt(i) && j>=0 ){
j=next[j];
}
if (bs.charAt(j+1)==bs.charAt(i)){
next[i]=j+1;
}else{
next[i]=-1;
}
}
return next;
}
@Test
public void test() {
// getNext("abcabcdabcabcd");
// getNextT("abadaba");
kmp("abadaba","adab");
}
public int[] getNextT(String s){
char[] c = s.toCharArray();
int[] next = new int[c.length];
next[0] = -1;
for (int i = 1; i < c.length; i++) {
int j = next[i-1];
while(j>0&&c[j+1]!=c[i]){
j = next[j];
}
if(c[j+1] == c[i]){
next[i] = j+1;
}else{
next[i] = -1;
}
}
return next;
}
@Test
public void test2() {
// getNext("abcabcdabcabcd");
getNextx("abadaba");
// kmp("abadaba","adab");
}
public int[] getNextx(String s)
{
int[] next = new int[s.length()];
next[0] = -1;
int i = 0, j = -1;
while (i < s.length()-1)
{
if (j == -1 || s.charAt(i) == s.charAt(j))
{
++i;
++j;
next[i] = j;
}
else{
j = next[j];
}
}
return next;
}
}