int[] prefixTable(String pattern) {
int[] prefix = new int[pattern.length()];
for (int i = 1, j = 0; i < pattern.length(); i++) {
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) j = prefix[j - 1];
if (pattern.charAt(i) == pattern.charAt(j)) j++;
prefix[i] = j;
}
return prefix;
}
def prefix_table(pattern: str) -> list[int]:
prefix = [0] * len(pattern)
j = 0
for i in range(1, len(pattern)):
while j and pattern[i] != pattern[j]:
j = prefix[j - 1]
if pattern[i] == pattern[j]:
j += 1
prefix[i] = j
return prefix
def prefixTable(pattern: String): Array[Int] =
val prefix = Array.fill(pattern.length)(0)
var j = 0
for i <- 1 until pattern.length do
while j > 0 && pattern(i) != pattern(j) do j = prefix(j - 1)
if pattern(i) == pattern(j) then j += 1
prefix(i) = j
prefix
std::vector<int> prefixTable(const std::string& pattern) {
std::vector<int> prefix(pattern.size());
for (int i = 1, j = 0; i < pattern.size(); i++) {
while (j > 0 && pattern[i] != pattern[j]) j = prefix[j - 1];
if (pattern[i] == pattern[j]) j++;
prefix[i] = j;
}
return prefix;
}