1   /**
2    * Copyright (c) 2000-2010 Liferay, Inc. All rights reserved.
3    *
4    * The contents of this file are subject to the terms of the Liferay Enterprise
5    * Subscription License ("License"). You may not use this file except in
6    * compliance with the License. You can obtain a copy of the License by
7    * contacting Liferay, Inc. See the License for the specific language governing
8    * permissions and limitations under the License, including but not limited to
9    * distribution rights of the Software.
10   *
11   *
12   *
13   */
14  
15  package com.liferay.portal.kernel.util;
16  
17  /**
18   * <a href="KMPSearch.java.html"><b><i>View Source</i></b></a>
19   *
20   * <p>
21   * See http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm.
22   * </p>
23   *
24   * @author Shuyang Zhou
25   */
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 }