Factorize string into Lyndon words: Difference between revisions
Factorize string into Lyndon words (view source)
Revision as of 01:08, 31 January 2024
, 3 months agoAdd Scala implementation
(→{{header|MATLAB}}: fix typo) |
(Add Scala implementation) |
||
Line 178:
<pre>
["011", "01", "0011", "00101101", "0010110011010011", "00101100110100101101001100101101", "001011001101001011010011001011001101001100101101", "001011001101", "001"]
</pre>
=={{header|Scala}}==
{{trans|Python}}
<syntaxhighlight lang="Scala">
object ChenFoxLyndonFactorization extends App {
def chenFoxLyndonFactorization(s: String): List[String] = {
val n = s.length
var i = 0
var factorization = List[String]()
while (i < n) {
var j = i + 1
var k = i
while (j < n && s.charAt(k) <= s.charAt(j)) {
if (s.charAt(k) < s.charAt(j)) {
k = i
} else {
k += 1
}
j += 1
}
while (i <= k) {
factorization = factorization :+ s.substring(i, i + j - k)
i += j - k
}
}
assert(s == factorization.mkString)
factorization
}
var m = "0"
for (i <- 0 until 7) {
val m0 = m
m = m.replace('0', 'a').replace('1', '0').replace('a', '1')
m = m0 + m
}
println(chenFoxLyndonFactorization(m))
}
</syntaxhighlight>
{{out}}
<pre>
List(011, 01, 0011, 00101101, 0010110011010011, 00101100110100101101001100101101, 001011001101001011010011001011001101001100101101, 001011001101, 001)
</pre>
| |||