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 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 }