Fast algorithms for Abelian periods in words and greatest common divisor queries

详细信息查看全文

文摘

class="label">•: We present a linear-time algorithm computing all full Abelian periods of a word.
class="label">•: We show fast randomized and deterministic algorithms computing all Abelian periods.
class="label">•: We obtain class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022000016300824&_mathId=si249.gif&_user=111111111&_pii=S0022000016300824&_rdoc=1&_issn=00220000&md5=e5207a3856b653afb6bda83ff5e3695a" title="Click to view the MathML source">O(1)class="mathContainer hidden">class="mathCode"> $O (1)$ -time GCD queries with arguments at most n with class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022000016300824&_mathId=si2.gif&_user=111111111&_pii=S0022000016300824&_rdoc=1&_issn=00220000&md5=779a45adf67ef0c5390c92c8399dd5e9" title="Click to view the MathML source">O(n)class="mathContainer hidden">class="mathCode"> $O (n)$ preprocessing time.

地址：北京市海淀区学院路29号邮编：100083

电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700