1
14
15 package com.liferay.portal.kernel.util;
16
17
26 public class KMPSearch {
27
28 public static int[] generateNexts(byte[] pattern) {
29 int length = pattern.length;
30
31 int[] nexts = new int[length];
32
33 nexts[0] = -1;
34
35 int i = 0;
36 int j = -1;
37
38 while (i < length - 1) {
39 if ((j == -1) || (pattern[i] == pattern[j])) {
40 i++;
41 j++;
42
43 nexts[i] = j;
44 }
45 else {
46 j = nexts[j];
47 }
48 }
49
50 return nexts;
51 }
52
53 public static int[] generateNexts(char[] pattern) {
54 int length = pattern.length;
55
56 int[] nexts = new int[length];
57
58 nexts[0] = -1;
59
60 int i = 0;
61 int j = -1;
62
63 while (i < length - 1) {
64 if ((j == -1) || (pattern[i] == pattern[j])) {
65 i++;
66 j++;
67
68 nexts[i] = j;
69 }
70 else {
71 j = nexts[j];
72 }
73 }
74
75 return nexts;
76 }
77
78 public static int[] generateNexts(CharSequence pattern) {
79 int length = pattern.length();
80
81 int[] nexts = new int[length];
82
83 nexts[0] = -1;
84
85 int i = 0;
86 int j = -1;
87
88 while (i < length - 1) {
89 if ((j == -1) || (pattern.charAt(i) == pattern.charAt(j))) {
90 i++;
91 j++;
92
93 nexts[i] = j;
94 }
95 else {
96 j = nexts[j];
97 }
98 }
99
100 return nexts;
101 }
102
103 public static int search(byte[] text, byte[] pattern) {
104 int[] nexts = generateNexts(pattern);
105
106 return search(text, 0, text.length, pattern, nexts);
107 }
108
109 public static int search(byte[] text, byte[] pattern, int[] nexts) {
110 return search(text, 0, text.length, pattern, nexts);
111 }
112
113 public static int search(
114 byte[] text, int offset, byte[] pattern, int[] nexts) {
115
116 return search(text, offset, text.length - offset, pattern, nexts);
117 }
118
119 public static int search(
120 byte[] text, int offset, int length, byte[] pattern, int[] nexts) {
121
122 int patternLength = pattern.length;
123
124 int i = 0;
125 int j = 0;
126
127 while (i < length && j < patternLength) {
128 if ((j == -1) || (text[i + offset] == pattern[j])) {
129 i++;
130 j++;
131 }
132 else {
133 j = nexts[j];
134 }
135 }
136
137 if (j >= patternLength) {
138 return i - patternLength + offset;
139 }
140 else {
141 return -1;
142 }
143 }
144
145 public static int search(char[] text, char[] pattern) {
146 int[] nexts = generateNexts(pattern);
147
148 return search(text, 0, text.length, pattern, nexts);
149 }
150
151 public static int search(char[] text, char[] pattern, int[] nexts) {
152 return search(text, 0, text.length, pattern, nexts);
153 }
154
155 public static int search(
156 char[] text, int offset, char[] pattern, int[] nexts) {
157
158 return search(text, offset, text.length - offset, pattern, nexts);
159 }
160
161 public static int search(
162 char[] text, int offset, int length, char[] pattern, int[] nexts) {
163
164 int patternLength = pattern.length;
165
166 int i = 0;
167 int j = 0;
168
169 while (i < length && j < patternLength) {
170 if ((j == -1) || (text[i + offset] == pattern[j])) {
171 i++;
172 j++;
173 }
174 else {
175 j = nexts[j];
176 }
177 }
178
179 if (j >= patternLength) {
180 return i - patternLength + offset;
181 }
182 else {
183 return -1;
184 }
185 }
186
187 public static int search(CharSequence text, CharSequence pattern) {
188 int[] nexts = generateNexts(pattern);
189
190 return search(text, 0, text.length(), pattern, nexts);
191 }
192
193 public static int search(CharSequence text, CharSequence pattern,
194 int[] nexts) {
195
196 return search(text, 0, text.length(), pattern, nexts);
197 }
198
199 public static int search(
200 CharSequence text, int offset, CharSequence pattern, int[] nexts) {
201
202 return search(text, offset, text.length() - offset, pattern, nexts);
203 }
204
205 public static int search(
206 CharSequence text, int offset, int length, CharSequence pattern,
207 int[] nexts) {
208
209 int patternLength = pattern.length();
210
211 int i = 0;
212 int j = 0;
213
214 while (i < length && j < patternLength) {
215 if ((j == -1) || (text.charAt(i + offset) == pattern.charAt(j))) {
216 i++;
217 j++;
218 }
219 else {
220 j = nexts[j];
221 }
222 }
223
224 if (j >= patternLength) {
225 return i - patternLength + offset;
226 }
227 else {
228 return -1;
229 }
230 }
231
232 }