1   /**
2    * Copyright (c) 2000-2009 Liferay, Inc. All rights reserved.
3    *
4    *
5    *
6    *
7    * The contents of this file are subject to the terms of the Liferay Enterprise
8    * Subscription License ("License"). You may not use this file except in
9    * compliance with the License. You can obtain a copy of the License by
10   * contacting Liferay, Inc. See the License for the specific language governing
11   * permissions and limitations under the License, including but not limited to
12   * distribution rights of the Software.
13   *
14   * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15   * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16   * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17   * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18   * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19   * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
20   * SOFTWARE.
21   */
22  
23  package com.liferay.portal.kernel.util;
24  
25  /**
26   * <a href="KMPSearch.java.html"><b><i>View Source</i></b></a>
27   *
28   * <p>
29   * See http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm.
30   * </p>
31   *
32   * @author Shuyang Zhou
33   */
34  public class KMPSearch {
35  
36      public static int[] generateNexts(byte[] pattern) {
37          int length = pattern.length;
38  
39          int[] nexts = new int[length];
40  
41          nexts[0] = -1;
42  
43          int i = 0;
44          int j = -1;
45  
46          while (i < length - 1) {
47              if ((j == -1) || (pattern[i] == pattern[j])) {
48                  i++;
49                  j++;
50  
51                  nexts[i] = j;
52              }
53              else {
54                  j = nexts[j];
55              }
56          }
57  
58          return nexts;
59      }
60  
61      public static int[] generateNexts(char[] pattern) {
62          int length = pattern.length;
63  
64          int[] nexts = new int[length];
65  
66          nexts[0] = -1;
67  
68          int i = 0;
69          int j = -1;
70  
71          while (i < length - 1) {
72              if ((j == -1) || (pattern[i] == pattern[j])) {
73                  i++;
74                  j++;
75  
76                  nexts[i] = j;
77              }
78              else {
79                  j = nexts[j];
80              }
81          }
82  
83          return nexts;
84      }
85  
86      public static int search(byte[] text, byte[] pattern) {
87          int[] nexts = generateNexts(pattern);
88  
89          return search(text, 0, text.length, pattern, nexts);
90      }
91  
92      public static int search(byte[] text, byte[] pattern, int[] nexts) {
93          return search(text, 0, text.length, pattern, nexts);
94      }
95  
96      public static int search(
97          byte[] text, int offset, byte[] pattern, int[] nexts) {
98  
99          return search(text, offset, text.length - offset, pattern, nexts);
100     }
101 
102     public static int search(
103         byte[] text, int offset, int length, byte[] pattern, int[] nexts) {
104 
105         int patternLength = pattern.length;
106 
107         int i = 0;
108         int j = 0;
109 
110         while (i < length && j < patternLength) {
111             if ((j == -1) || (text[i + offset] == pattern[j])) {
112                 i++;
113                 j++;
114             }
115             else {
116                 j = nexts[j];
117             }
118         }
119 
120         if (j >= patternLength) {
121             return i - patternLength + offset;
122         }
123         else {
124             return -1;
125         }
126     }
127 
128     public static int search(char[] text, char[] pattern) {
129         int[] nexts = generateNexts(pattern);
130 
131         return search(text, 0, text.length, pattern, nexts);
132     }
133 
134     public static int search(char[] text, char[] pattern, int[] nexts) {
135         return search(text, 0, text.length, pattern, nexts);
136     }
137 
138     public static int search(
139         char[] text, int offset, char[] pattern, int[] nexts) {
140 
141         return search(text, offset, text.length - offset, pattern, nexts);
142     }
143 
144     public static int search(
145         char[] text, int offset, int length, char[] pattern, int[] nexts) {
146 
147         int patternLength = pattern.length;
148 
149         int i = 0;
150         int j = 0;
151 
152         while (i < length && j < patternLength) {
153             if ((j == -1) || (text[i + offset] == pattern[j])) {
154                 i++;
155                 j++;
156             }
157             else {
158                 j = nexts[j];
159             }
160         }
161 
162         if (j >= patternLength) {
163             return i - patternLength + offset;
164         }
165         else {
166             return -1;
167         }
168     }
169 
170 }