0
$\begingroup$

This might be an irritating, naive question, but please bear with me. If an algorithm/code solves the string matching problem for a binary string, does not it imply that the algo/code actually solves the string matching problem in general?

Because, in hardware everything is converted to 0 and 1 and then calculation is done.

The idea is binary string matching could be easier than the general case, so if we have a faster algorithm we (may) use that in machine code, and obtain faster general solution.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
0
$\begingroup$

Computers work with string encodings which are literally mapping of symbols to binary strings. As a practical matter, real computers use fixed size registers and and string matching algorithms implemented on those computers are working with register-sized data anyways.

Of course you can build a special purpose computer for bitstring processing (eg. special hardware for processing say DNA sequences), you are only going to get a constant factor improvement, if any. i.e., the same algorithm operating on bitstrings and general strings will have same asymptotic complexity.

Improve this answer
$\endgroup$
0
$\begingroup$

String matching performed bit by bit would be much slower than character by character, because a character is made of 8 or 16 bits and a processor can handle them in a single go.

Also note that string matching is based on comparisons, that conclude "equal" or "different", whether the symbols are bits or characters (or anything else). For this reason binary string matching is not easier than character string matching.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.