t are called
k-Abelian equivalent (shortened to
k-equivalent in the following) for a positive integer
k if the following conditions hold:
- The length-
- The length-
- The strings
thave the same multisets of length-
kcontiguous substrings. In other words, every string of length
koccurs an equal number of times in
t. Overlapping occurrences are counted as distinct.
k-equivalent strings are always
k > 1, and the third condition implies that
t have the same length.
It is also known, and possibly useful, that the three conditions above are equivalent to the following one:
- Every non-empty string of length
k-1occurs an equal number of times in
For example, consider the strings
s = "abbaaabb" and
t = "aabbaabb".
Because the strings have the same number of each character, 4 of
a and 4 of
b, they are
Their first and last characters are the same (both strings begin with
a and end with
b), so the first two conditions are satisfied.
2 substrings of
aa (occurs twice),
ba (once), and
bb (twice), and those of
t are exactly the same.
This means that the strings are
However, since their second letters are different, the strings are not
Two alphanumeric strings
t of the same length
n > 0.
The largest integer
n (inclusive) such that
If no such
k exists, the output is
In the above example, the correct output would be
You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. Crashing on malformed input is perfectly fine.
"abc" "def" -> 0 "abbaabbb" "aabbbaab" -> 0 "abbaaabb" "aabbbaab" -> 2 "abbaaabb" "aabbaabb" -> 2 "aaabbaabb" "aabbaaabb" -> 3 "aaabbaabb" "aaabbaabb" -> 9 "abbabaabbaababbabaababbaabbabaab" "abbabaabbaababbaabbabaababbabaab" -> 9 "yzxyxx" "yxyzxx" -> 2 "xxxxxyxxxx" "xxxxyxxxxx" -> 5
"abbaaabb" "aabbbaab"= 1? The prefixes
aand the suffixes
bare the same, and the substrings
bbappear each twice, and the substring
baappears once in each string. \$\endgroup\$
k-1prefixes of s and t are equal." \$\endgroup\$