data structures - Search for cyclic strings -

data structures - Search for cyclic strings -

i looking efficient way store binary strings in info construction (insert function) , when getting string want check if cyclic string of given string in structure.

i thought storing input strings in trie when trying determine whether cyclic string of string got inserted trie means |s| searches in trie possible cyclic strings.

is there way more efficiently while place complexity in trie?

note: when cyclic strings of string mean illustration cyclic strings of 1011 are: 0111, 1110, 1101, 1011

can come canonicalizing function cyclic strings based on following:

find largest run of zeroes. rotate string that run of zeroes @ front. for each run of zeroes of equal size, see if rotating front end produces lexicographically lesser string , if utilize that.

this canonicalize in equivalence class (1011, 1101, 1110, 0111) lexicographically to the lowest degree value: 0111.

0101010101 thorny instance algo not perform well, if bits randomly distributed, should work in practice long strings.

you can hash based on canonical form or utilize trie include empty string , strings start 0 , single trie run reply question.

edit:

if have string of length |s| can take lot of time find to the lowest degree lexicographically value..how much time take?

that's why said 010101.... value performs badly. let's string of length n , longest run of 1's of length r. if bits randomly distributed, length of longest run o(log n) according "distribution of longest run".

the time find longest run o(n). can implement shifting using offset instead of buffer copy, should o(1). number of runs worst case o(n / m).

then, time step 3 should

find other long runs: 1 o(n) pass o(log n) storage average case, o(n) worst case for each run: o(log n) average case, o(n) worst case   shift , compare lexicographically: o(log n) average case since comparisons of randomly chosen strings fail early, o(n) worst case.

this leads worst case of o(n²) average case of o(n + log² n) ≅ o(n).

string data-structures trie cyclic