1   /**
2    * Copyright (c) 2000-2010 Liferay, Inc. All rights reserved.
3    *
4    * This library is free software; you can redistribute it and/or modify it under
5    * the terms of the GNU Lesser General Public License as published by the Free
6    * Software Foundation; either version 2.1 of the License, or (at your option)
7    * any later version.
8    *
9    * This library is distributed in the hope that it will be useful, but WITHOUT
10   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11   * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
12   * details.
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 search(byte[] text, byte[] pattern) {
79          int[] nexts = generateNexts(pattern);
80  
81          return search(text, 0, text.length, pattern, nexts);
82      }
83  
84      public static int search(byte[] text, byte[] pattern, int[] nexts) {
85          return search(text, 0, text.length, pattern, nexts);
86      }
87  
88      public static int search(
89          byte[] text, int offset, byte[] pattern, int[] nexts) {
90  
91          return search(text, offset, text.length - offset, pattern, nexts);
92      }
93  
94      public static int search(
95          byte[] text, int offset, int length, byte[] pattern, int[] nexts) {
96  
97          int patternLength = pattern.length;
98  
99          int i = 0;
100         int j = 0;
101 
102         while (i < length && j < patternLength) {
103             if ((j == -1) || (text[i + offset] == pattern[j])) {
104                 i++;
105                 j++;
106             }
107             else {
108                 j = nexts[j];
109             }
110         }
111 
112         if (j >= patternLength) {
113             return i - patternLength + offset;
114         }
115         else {
116             return -1;
117         }
118     }
119 
120     public static int search(char[] text, char[] pattern) {
121         int[] nexts = generateNexts(pattern);
122 
123         return search(text, 0, text.length, pattern, nexts);
124     }
125 
126     public static int search(char[] text, char[] pattern, int[] nexts) {
127         return search(text, 0, text.length, pattern, nexts);
128     }
129 
130     public static int search(
131         char[] text, int offset, char[] pattern, int[] nexts) {
132 
133         return search(text, offset, text.length - offset, pattern, nexts);
134     }
135 
136     public static int search(
137         char[] text, int offset, int length, char[] pattern, int[] nexts) {
138 
139         int patternLength = pattern.length;
140 
141         int i = 0;
142         int j = 0;
143 
144         while (i < length && j < patternLength) {
145             if ((j == -1) || (text[i + offset] == pattern[j])) {
146                 i++;
147                 j++;
148             }
149             else {
150                 j = nexts[j];
151             }
152         }
153 
154         if (j >= patternLength) {
155             return i - patternLength + offset;
156         }
157         else {
158             return -1;
159         }
160     }
161 
162 }