Background
Two strings s
and 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-
k-1
prefixes ofs
andt
are equal. - The length-
k-1
suffixes ofs
andt
are equal. - The strings
s
andt
have the same multisets of length-k
contiguous substrings. In other words, every string of lengthk
occurs an equal number of times ins
andt
. Overlapping occurrences are counted as distinct.
Note that k
-equivalent strings are always k-1
-equivalent if k > 1
, and the third condition implies that s
and 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
ork-1
occurs an equal number of times ins
andt
.
An Example
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 1
-equivalent.
Consider then 2
-equivalence.
Their first and last characters are the same (both strings begin with a
and end with b
), so the first two conditions are satisfied.
The length-2
substrings of s
are aa
(occurs twice), ab
(twice), ba
(once), and bb
(twice), and those of t
are exactly the same.
This means that the strings are 2
-equivalent.
However, since their second letters are different, the strings are not 3
-equivalent.
Input
Two alphanumeric strings s
and t
of the same length n > 0
.
Output
The largest integer k
between 1
and n
(inclusive) such that s
and t
are k
-equivalent.
If no such k
exists, the output is 0
.
In the above example, the correct output would be 2
.
Rules
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.
Test Cases
"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 prefixesa
,a
and the suffixesb
,b
are the same, and the substringsaa
,ab
,bb
appear each twice, and the substringba
appears once in each string. \$\endgroup\$k-1
prefixes of s and t are equal." \$\endgroup\$