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.