1
22
23 package com.liferay.portal.kernel.util;
24
25
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 }