Multiple sub-string searching
View Patent ↗A method for searching for multiple sub-strings of an original text is provided. A search query is received, wherein the search query includes a plurality of sub-strings. A hash array is allocated. The hash array has a size based, at least in part, on the plurality of sub-strings and an original text. The hash array is populated with a plurality of hash values, wherein the plurality of hash values are generated using a rolling hash function, and wherein each of the plurality of hash values corresponds to a portion of the original text. A plurality of sub-string values are computed based on the plurality of sub-strings. Each of the plurality of sub-strings are determined to occur in the original text based, at least in part, on searching the hash array for the plurality of sub-string values.
1. A computer program product comprising:
a computer readable storage medium and program instructions stored on the computer readable storage medium, the program instructions comprising:
program instructions to receive a search query of an original text, wherein:
the search query comprises a plurality of sub-strings including a first sub-string of a first length and a second sub-string of a second length; and
the first length is different than the second length;
program instructions to determine a number of different sub-string lengths present within the plurality of sub-strings;
program instructions to allocate a hash array having a number of entries, wherein the number of entries is based on (i) the determined number of different sub-string lengths and (ii) a character length of the original text;
program instructions to populate the hash array with a plurality of hash values, wherein:
the plurality of hash values are generated using: (i) a first rolling hash function equal to the first length, and a second rolling hash function equal to the second length; and
each of the plurality of hash values corresponds to a portion of the original text;
program instructions to compute a plurality of sub-string values based, at least in part, on the plurality of sub-strings; and
program instructions to determine whether each of the plurality of sub-strings occurs in the original text based on searching the hash array for the plurality of sub-string values.
2. The computer program product of claim 1 , wherein program instructions to search the hash array for plurality of sub-string values comprise:
program instructions to initialize a TRT array, wherein the TRT array comprises a plurality of action codes;
program instructions to flag one or more action codes based on the plurality of sub-string values; and
program instructions to compare the TRT array and the hash array.
3. The computer program product of claim 1 , wherein program instructions to populate the hash array comprise:
program instructions to calculate a first hash sequence based, at least in part, on portions of the original text having lengths equal to the first length;
program instructions to calculate a second hash sequence based, at least in part, on portions of the original text having lengths equal to the second length; and
program instructions to compile the hash array by alternately interleaving each hash value of the first hash sequence and the second hash sequence.
4. A computer system, the computer system comprising:
one or more computer processors;
one or more computer readable storage media;
program instructions stored on the computer readable storage media for execution by at least one of the one or more processors, the program instructions comprising:
program instructions to receive a search query of an original text, wherein:
the search query comprises a plurality of sub-strings including a first sub-string of a first length and a second sub-string of a second length; and
the first length is different than the second length;
program instructions to determine a number of different sub-string lengths present within the plurality of sub-strings;
program instructions to allocate a hash array having a number of entries, wherein the number of entries is based on (i) the determined number of different sub-string lengths and (ii) a character length of the original text;
program instructions to populate the hash array with a plurality of hash values, wherein:
the plurality of hash values are generated using: (i) a first rolling hash function equal to the first length, and a second rolling hash function equal to the second length; and
each of the plurality of hash values corresponds to a portion of the original text;
program instructions to compute a plurality of sub-string values based, at least in part, on the plurality of sub-strings; and
program instructions to determine whether each of the plurality of sub-strings occurs in the original text based on searching the hash array for the plurality of sub-string values.
5. The computer system of claim 4 , wherein program instructions to search the hash array for plurality of sub-string values comprise:
program instructions to initialize a TRT array, wherein the TRT array comprises a plurality of action codes;
program instructions to flag one or more action codes based on the plurality of sub-string values; and
program instructions to compare the TRT array and the hash array.
6. The computer program product of claim 1 , wherein the plurality of sub-strings further comprises a third sub-string of the first length.