Wednesday, May 09, 2012

String comparison

Whenever we need to compare strings, what we can use it?

Text: abc bcd bcd abc
Pattern: abc bcd
[Ex: BHTML & BCSS codeforces problem]

we need to compare text and pattern using strcmp. But naive string
comparison takes more time.

Solution 1)we can use RobinKarp or KMP algorithm to reduce time. or
else we can do the following way to avoid the problem.

How to avoid this:

we can use array to store the strings without duplication.

Array [][]={ "abc","bcd"}

Text Array: {0,1,1,0}
Pattern Array: {0,1}

then apply naive comparison in TextArray and pattern Array.

Solution 2)Compare to string array, int array comparison will takes less time.

Solution 3) if we are using array also, we need to compare all the
elements in array on worst case to add or lookup.
in this case, what we can do to improve this ?

We can use Binary Search Tree to store strings. if the given
string is less than the root string,
we need to search it from left child of the string.if it is greater
than or equal to the rootstring, we need to search the
right child of the root.

STL map is using RedBlack tree implementation. we can make
use of map to store strings.STL map can also be used for Hashtable.

No comments: