CODEWITHSUNDEEP
calgorithm
Krzysztof Lewko
Krzysztof Lewko

Reputation: 1002

C Text algorithms

I'm curious about few things about text algorithms.

For example we have binary word : 1011101110001101 And how to search for specific fixed subsequences in this word ?

For example how to find longest fixed subsequence(lets call it LFS) in word which has same amount of 1's and 0's ?

And another, how to find LFS with more 1's than 0's in it ?

Example : word :1001010 we are searching for LFS with same amount of 1's and 0's.

So this LFS would be 100101

But with more 1's than 0's we'll have : 101

How to solve this faster than O(n^2)?

Chris.

Upvotes: 2

Views: 206

Answers (1)

Yochai Timmer
Yochai Timmer

Reputation: 49261

You can make a Trie out of the input.

That will help you find LFS strings.

You can change the creation algorithm to count 1s and 0s, and then you'll easily find those numbers on the substring nodes.

Look at Suffix Tree as well..

Creation = O(n)
For the search, you'll probably do something like BFS which also be like O(N)

Upvotes: 4

Related Questions