\/\/ Construct a table with table[i] as the length of the longest prefix of the substring 0..i\n\/\/ create a table of size equal to the length of `str`\n\/\/ table[i] will store the prefix of the longest prefix of the substring str[0..i]\n\/\/ the longest prefix of the substring str[0] has length\n\/\/ for the substrings the following substrings, we have two cases\n\/\/ case 1. the current character doesn't match the last character of the longest prefix\n\/\/ if that is the case, we have to backtrack, and try find a character that will be equal to the current character\n\/\/ if we reach 0, then we couldn't find a chracter\n\/\/ case 2. The last character of the longest prefix matches the current character in `str`\n\/\/ if that is the case, we know that the longest prefix at position i has one more character.\n\/\/ for example consider `.` be any character not contained in the set [a.c]\n\/\/ str = abc....abc\n\/\/ consider `i` to be the last character `c` in `str`\n\/\/ maxPrefix = will be 2 (the first `c` in `str`)\n\/\/ maxPrefix now will be 3\n\/\/ so the max prefix for table[9] is 3\nfunction makeTable(str) {\n \n \n var table = new Array(str.length);\n var maxPrefix = 0;\n \n table[0] = 0;\n \n \n for (var i = 1; i < str.length; i++) {\n while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) {\n \n maxPrefix = table[maxPrefix - 1];\n }\n \n if (str.charAt(maxPrefix) === str.charAt(i)) {\n maxPrefix++;\n }\n table[i] = maxPrefix;\n }\n return table;\n }\n \n\/\/ Find all the words that matches in a given string `str`\n\/\/ this algorithm is based on the Knuth\u2013Morris\u2013Pratt algorithm. Its beauty consists in that it performs the matching in O(n)\n\/\/ find the prefix table in O(n)\n\/\/ `j` is the index in `word(P)`\n\/\/ `i` is the index in `str(S)`\n\/\/ Case 1. S[i] == P[j] so we move to the next index in `S` and `P`\n\/\/ Case 2. `j` is equal to the length of `P`\n\/\/ that means that we reached the end of `P` and thus we found a match\n\/\/ Next we have to update `j` because we want to save some time\n\/\/ instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far.\n\/\/ j-1 means the last character of `P` because j is actually `P.length`\n\/\/ e.g.\n\/\/ S = a b a b d e\n\/\/ P = `a b`a b\n\/\/ we will jump to `a b` and we will compare d and a in the next iteration\n\/\/ a b a b `d` e\n\/\/ a b `a` b\n\/\/ Case 3.\n\/\/ S[i] != P[j] There's a mismatch!\n\/\/ if we have found at least a character in common, do the same thing as in case 2\n\/\/ otherwise, j = 0, and we can move to the next character S[i+1]function kmpMatching(str, word) {\n \n var prefixes = makeTable(word);\n var matches = [];\n \n \n var j = 0;\n var i = 0;\n while (i < str.length) {\n \n if (str.charAt(i) === word.charAt(j)) {\n i++;\n j++;\n }\n \n if (j === word.length) {\n matches.push(i-j);\n \n j = prefixes[j-1];\n }\n \n else if (str.charAt(i) !== word.charAt(j)) {\n \n if (j !== 0) {\n j = prefixes[j-1];\n } else {\n \n i++;\n }\n }\n }\n \n return matches;\n }\n\nconsole.log(kmpMatching(\"it implies that it is very important\",\"impo\"))\n\noutput: [27]\n<\/pre>\n\n\n\nWe can implement these algorithms in real world applications.Hope it helps.There are many other algorithms to use. But for a start these might help.<\/p>\n\n\n\n
Happy coding.....<\/p>\n","post_title":"Searching Algorithms in JavaScript","post_excerpt":"The Searching Algorithm can be implemented with other languages as well. But here we will work with JavaScript to solve the Searching Algorithms. These algorithms are used to handle or work with the search related task in our projects or any applications that require searching. Searching is made easier by these algorithms. Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them.","post_status":"publish","comment_status":"open","ping_status":"open","post_password":"","post_name":"searching-algorithms-in-javascript","to_ping":"","pinged":"","post_modified":"2024-11-14 04:16:56","post_modified_gmt":"2024-11-14 04:16:56","post_content_filtered":"","post_parent":0,"guid":"https:\/\/blogue.tech\/?p=277","menu_order":0,"post_type":"post","post_mime_type":"","comment_count":"0","filter":"raw"}],"next":false,"prev":false,"total_page":1},"paged":1,"column_class":"jeg_col_3o3","class":"jnews_block_3"};
\nBut this way we have to search each and every word from the begining in case of multiple data to search.The Knuth-Morris-Pratt string search algorithm<\/a> or KMP algorithm is an algorithm for finding a substring within another string that uses information calculated about the substring to speed up the search process.Before looking through the text to be searched, a table of jump lengths is calculated from the search string. Rather than iterating through the whole string, you can determine how many characters to skip over based on the structure of the word being searched for. As you scan through the search text and you find a mismatch, you can start comparing characters again from the last matching substring between the search term and the search text.E.g. if you are searching through \"Hello world how ya doin?\" for the words \u201cold world new\u201d, every time you find an instance of \u201dold world new\u201d that isn\u2019t followed by a line-break, you can skip the characters of checking the string and restart from the beginning of your words, because you know that they can\u2019t occur again within that span because you have already checked those and they don\u2019t match the begging of the search words. Basically you already know that index is the next occurence of world, so you can start again from there.<\/p>\n\n\n\n
\/\/ Construct a table with table[i] as the length of the longest prefix of the substring 0..i\n\/\/ create a table of size equal to the length of `str`\n\/\/ table[i] will store the prefix of the longest prefix of the substring str[0..i]\n\/\/ the longest prefix of the substring str[0] has length\n\/\/ for the substrings the following substrings, we have two cases\n\/\/ case 1. the current character doesn't match the last character of the longest prefix\n\/\/ if that is the case, we have to backtrack, and try find a character that will be equal to the current character\n\/\/ if we reach 0, then we couldn't find a chracter\n\/\/ case 2. The last character of the longest prefix matches the current character in `str`\n\/\/ if that is the case, we know that the longest prefix at position i has one more character.\n\/\/ for example consider `.` be any character not contained in the set [a.c]\n\/\/ str = abc....abc\n\/\/ consider `i` to be the last character `c` in `str`\n\/\/ maxPrefix = will be 2 (the first `c` in `str`)\n\/\/ maxPrefix now will be 3\n\/\/ so the max prefix for table[9] is 3\nfunction makeTable(str) {\n \n \n var table = new Array(str.length);\n var maxPrefix = 0;\n \n table[0] = 0;\n \n \n for (var i = 1; i < str.length; i++) {\n while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) {\n \n maxPrefix = table[maxPrefix - 1];\n }\n \n if (str.charAt(maxPrefix) === str.charAt(i)) {\n maxPrefix++;\n }\n table[i] = maxPrefix;\n }\n return table;\n }\n \n\/\/ Find all the words that matches in a given string `str`\n\/\/ this algorithm is based on the Knuth\u2013Morris\u2013Pratt algorithm. Its beauty consists in that it performs the matching in O(n)\n\/\/ find the prefix table in O(n)\n\/\/ `j` is the index in `word(P)`\n\/\/ `i` is the index in `str(S)`\n\/\/ Case 1. S[i] == P[j] so we move to the next index in `S` and `P`\n\/\/ Case 2. `j` is equal to the length of `P`\n\/\/ that means that we reached the end of `P` and thus we found a match\n\/\/ Next we have to update `j` because we want to save some time\n\/\/ instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far.\n\/\/ j-1 means the last character of `P` because j is actually `P.length`\n\/\/ e.g.\n\/\/ S = a b a b d e\n\/\/ P = `a b`a b\n\/\/ we will jump to `a b` and we will compare d and a in the next iteration\n\/\/ a b a b `d` e\n\/\/ a b `a` b\n\/\/ Case 3.\n\/\/ S[i] != P[j] There's a mismatch!\n\/\/ if we have found at least a character in common, do the same thing as in case 2\n\/\/ otherwise, j = 0, and we can move to the next character S[i+1]function kmpMatching(str, word) {\n \n var prefixes = makeTable(word);\n var matches = [];\n \n \n var j = 0;\n var i = 0;\n while (i < str.length) {\n \n if (str.charAt(i) === word.charAt(j)) {\n i++;\n j++;\n }\n \n if (j === word.length) {\n matches.push(i-j);\n \n j = prefixes[j-1];\n }\n \n else if (str.charAt(i) !== word.charAt(j)) {\n \n if (j !== 0) {\n j = prefixes[j-1];\n } else {\n \n i++;\n }\n }\n }\n \n return matches;\n }\n\nconsole.log(kmpMatching(\"it implies that it is very important\",\"impo\"))\n\noutput: [27]\n<\/pre>\n\n\n\nWe can implement these algorithms in real world applications.Hope it helps.There are many other algorithms to use. But for a start these might help.<\/p>\n\n\n\n
Happy coding.....<\/p>\n","post_title":"Searching Algorithms in JavaScript","post_excerpt":"The Searching Algorithm can be implemented with other languages as well. But here we will work with JavaScript to solve the Searching Algorithms. These algorithms are used to handle or work with the search related task in our projects or any applications that require searching. Searching is made easier by these algorithms. Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them.","post_status":"publish","comment_status":"open","ping_status":"open","post_password":"","post_name":"searching-algorithms-in-javascript","to_ping":"","pinged":"","post_modified":"2024-11-14 04:16:56","post_modified_gmt":"2024-11-14 04:16:56","post_content_filtered":"","post_parent":0,"guid":"https:\/\/blogue.tech\/?p=277","menu_order":0,"post_type":"post","post_mime_type":"","comment_count":"0","filter":"raw"}],"next":false,"prev":false,"total_page":1},"paged":1,"column_class":"jeg_col_3o3","class":"jnews_block_3"};
\nfunction naiveSearch(str, word){\n var count = 0;\n for(var i = 0; i < str.length; i++){\n for(var j = 0; j < word.length; j++){\n if(word[j] !== str[i+j]) break;\n if(j === word.length - 1) count++;\n }\n }\n return count;\n}\n\n\nconsole.log(naiveSearch(\"search and find\", \"an\"))\n\noutput: [7]\n<\/pre>\n\n\n\nBut this way we have to search each and every word from the begining in case of multiple data to search.The Knuth-Morris-Pratt string search algorithm<\/a> or KMP algorithm is an algorithm for finding a substring within another string that uses information calculated about the substring to speed up the search process.Before looking through the text to be searched, a table of jump lengths is calculated from the search string. Rather than iterating through the whole string, you can determine how many characters to skip over based on the structure of the word being searched for. As you scan through the search text and you find a mismatch, you can start comparing characters again from the last matching substring between the search term and the search text.E.g. if you are searching through \"Hello world how ya doin?\" for the words \u201cold world new\u201d, every time you find an instance of \u201dold world new\u201d that isn\u2019t followed by a line-break, you can skip the characters of checking the string and restart from the beginning of your words, because you know that they can\u2019t occur again within that span because you have already checked those and they don\u2019t match the begging of the search words. Basically you already know that index is the next occurence of world, so you can start again from there.<\/p>\n\n\n\n
\/\/ Construct a table with table[i] as the length of the longest prefix of the substring 0..i\n\/\/ create a table of size equal to the length of `str`\n\/\/ table[i] will store the prefix of the longest prefix of the substring str[0..i]\n\/\/ the longest prefix of the substring str[0] has length\n\/\/ for the substrings the following substrings, we have two cases\n\/\/ case 1. the current character doesn't match the last character of the longest prefix\n\/\/ if that is the case, we have to backtrack, and try find a character that will be equal to the current character\n\/\/ if we reach 0, then we couldn't find a chracter\n\/\/ case 2. The last character of the longest prefix matches the current character in `str`\n\/\/ if that is the case, we know that the longest prefix at position i has one more character.\n\/\/ for example consider `.` be any character not contained in the set [a.c]\n\/\/ str = abc....abc\n\/\/ consider `i` to be the last character `c` in `str`\n\/\/ maxPrefix = will be 2 (the first `c` in `str`)\n\/\/ maxPrefix now will be 3\n\/\/ so the max prefix for table[9] is 3\nfunction makeTable(str) {\n \n \n var table = new Array(str.length);\n var maxPrefix = 0;\n \n table[0] = 0;\n \n \n for (var i = 1; i < str.length; i++) {\n while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) {\n \n maxPrefix = table[maxPrefix - 1];\n }\n \n if (str.charAt(maxPrefix) === str.charAt(i)) {\n maxPrefix++;\n }\n table[i] = maxPrefix;\n }\n return table;\n }\n \n\/\/ Find all the words that matches in a given string `str`\n\/\/ this algorithm is based on the Knuth\u2013Morris\u2013Pratt algorithm. Its beauty consists in that it performs the matching in O(n)\n\/\/ find the prefix table in O(n)\n\/\/ `j` is the index in `word(P)`\n\/\/ `i` is the index in `str(S)`\n\/\/ Case 1. S[i] == P[j] so we move to the next index in `S` and `P`\n\/\/ Case 2. `j` is equal to the length of `P`\n\/\/ that means that we reached the end of `P` and thus we found a match\n\/\/ Next we have to update `j` because we want to save some time\n\/\/ instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far.\n\/\/ j-1 means the last character of `P` because j is actually `P.length`\n\/\/ e.g.\n\/\/ S = a b a b d e\n\/\/ P = `a b`a b\n\/\/ we will jump to `a b` and we will compare d and a in the next iteration\n\/\/ a b a b `d` e\n\/\/ a b `a` b\n\/\/ Case 3.\n\/\/ S[i] != P[j] There's a mismatch!\n\/\/ if we have found at least a character in common, do the same thing as in case 2\n\/\/ otherwise, j = 0, and we can move to the next character S[i+1]function kmpMatching(str, word) {\n \n var prefixes = makeTable(word);\n var matches = [];\n \n \n var j = 0;\n var i = 0;\n while (i < str.length) {\n \n if (str.charAt(i) === word.charAt(j)) {\n i++;\n j++;\n }\n \n if (j === word.length) {\n matches.push(i-j);\n \n j = prefixes[j-1];\n }\n \n else if (str.charAt(i) !== word.charAt(j)) {\n \n if (j !== 0) {\n j = prefixes[j-1];\n } else {\n \n i++;\n }\n }\n }\n \n return matches;\n }\n\nconsole.log(kmpMatching(\"it implies that it is very important\",\"impo\"))\n\noutput: [27]\n<\/pre>\n\n\n\nWe can implement these algorithms in real world applications.Hope it helps.There are many other algorithms to use. But for a start these might help.<\/p>\n\n\n\n
Happy coding.....<\/p>\n","post_title":"Searching Algorithms in JavaScript","post_excerpt":"The Searching Algorithm can be implemented with other languages as well. But here we will work with JavaScript to solve the Searching Algorithms. These algorithms are used to handle or work with the search related task in our projects or any applications that require searching. Searching is made easier by these algorithms. Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them.","post_status":"publish","comment_status":"open","ping_status":"open","post_password":"","post_name":"searching-algorithms-in-javascript","to_ping":"","pinged":"","post_modified":"2024-11-14 04:16:56","post_modified_gmt":"2024-11-14 04:16:56","post_content_filtered":"","post_parent":0,"guid":"https:\/\/blogue.tech\/?p=277","menu_order":0,"post_type":"post","post_mime_type":"","comment_count":"0","filter":"raw"}],"next":false,"prev":false,"total_page":1},"paged":1,"column_class":"jeg_col_3o3","class":"jnews_block_3"};
\nReturn the count<\/li>\n<\/ul>\n\n\n\n function naiveSearch(str, word){\n var count = 0;\n for(var i = 0; i < str.length; i++){\n for(var j = 0; j < word.length; j++){\n if(word[j] !== str[i+j]) break;\n if(j === word.length - 1) count++;\n }\n }\n return count;\n}\n\n\nconsole.log(naiveSearch(\"search and find\", \"an\"))\n\noutput: [7]\n<\/pre>\n\n\n\nBut this way we have to search each and every word from the begining in case of multiple data to search.The Knuth-Morris-Pratt string search algorithm<\/a> or KMP algorithm is an algorithm for finding a substring within another string that uses information calculated about the substring to speed up the search process.Before looking through the text to be searched, a table of jump lengths is calculated from the search string. Rather than iterating through the whole string, you can determine how many characters to skip over based on the structure of the word being searched for. As you scan through the search text and you find a mismatch, you can start comparing characters again from the last matching substring between the search term and the search text.E.g. if you are searching through \"Hello world how ya doin?\" for the words \u201cold world new\u201d, every time you find an instance of \u201dold world new\u201d that isn\u2019t followed by a line-break, you can skip the characters of checking the string and restart from the beginning of your words, because you know that they can\u2019t occur again within that span because you have already checked those and they don\u2019t match the begging of the search words. Basically you already know that index is the next occurence of world, so you can start again from there.<\/p>\n\n\n\n
\/\/ Construct a table with table[i] as the length of the longest prefix of the substring 0..i\n\/\/ create a table of size equal to the length of `str`\n\/\/ table[i] will store the prefix of the longest prefix of the substring str[0..i]\n\/\/ the longest prefix of the substring str[0] has length\n\/\/ for the substrings the following substrings, we have two cases\n\/\/ case 1. the current character doesn't match the last character of the longest prefix\n\/\/ if that is the case, we have to backtrack, and try find a character that will be equal to the current character\n\/\/ if we reach 0, then we couldn't find a chracter\n\/\/ case 2. The last character of the longest prefix matches the current character in `str`\n\/\/ if that is the case, we know that the longest prefix at position i has one more character.\n\/\/ for example consider `.` be any character not contained in the set [a.c]\n\/\/ str = abc....abc\n\/\/ consider `i` to be the last character `c` in `str`\n\/\/ maxPrefix = will be 2 (the first `c` in `str`)\n\/\/ maxPrefix now will be 3\n\/\/ so the max prefix for table[9] is 3\nfunction makeTable(str) {\n \n \n var table = new Array(str.length);\n var maxPrefix = 0;\n \n table[0] = 0;\n \n \n for (var i = 1; i < str.length; i++) {\n while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) {\n \n maxPrefix = table[maxPrefix - 1];\n }\n \n if (str.charAt(maxPrefix) === str.charAt(i)) {\n maxPrefix++;\n }\n table[i] = maxPrefix;\n }\n return table;\n }\n \n\/\/ Find all the words that matches in a given string `str`\n\/\/ this algorithm is based on the Knuth\u2013Morris\u2013Pratt algorithm. Its beauty consists in that it performs the matching in O(n)\n\/\/ find the prefix table in O(n)\n\/\/ `j` is the index in `word(P)`\n\/\/ `i` is the index in `str(S)`\n\/\/ Case 1. S[i] == P[j] so we move to the next index in `S` and `P`\n\/\/ Case 2. `j` is equal to the length of `P`\n\/\/ that means that we reached the end of `P` and thus we found a match\n\/\/ Next we have to update `j` because we want to save some time\n\/\/ instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far.\n\/\/ j-1 means the last character of `P` because j is actually `P.length`\n\/\/ e.g.\n\/\/ S = a b a b d e\n\/\/ P = `a b`a b\n\/\/ we will jump to `a b` and we will compare d and a in the next iteration\n\/\/ a b a b `d` e\n\/\/ a b `a` b\n\/\/ Case 3.\n\/\/ S[i] != P[j] There's a mismatch!\n\/\/ if we have found at least a character in common, do the same thing as in case 2\n\/\/ otherwise, j = 0, and we can move to the next character S[i+1]function kmpMatching(str, word) {\n \n var prefixes = makeTable(word);\n var matches = [];\n \n \n var j = 0;\n var i = 0;\n while (i < str.length) {\n \n if (str.charAt(i) === word.charAt(j)) {\n i++;\n j++;\n }\n \n if (j === word.length) {\n matches.push(i-j);\n \n j = prefixes[j-1];\n }\n \n else if (str.charAt(i) !== word.charAt(j)) {\n \n if (j !== 0) {\n j = prefixes[j-1];\n } else {\n \n i++;\n }\n }\n }\n \n return matches;\n }\n\nconsole.log(kmpMatching(\"it implies that it is very important\",\"impo\"))\n\noutput: [27]\n<\/pre>\n\n\n\nWe can implement these algorithms in real world applications.Hope it helps.There are many other algorithms to use. But for a start these might help.<\/p>\n\n\n\n
Happy coding.....<\/p>\n","post_title":"Searching Algorithms in JavaScript","post_excerpt":"The Searching Algorithm can be implemented with other languages as well. But here we will work with JavaScript to solve the Searching Algorithms. These algorithms are used to handle or work with the search related task in our projects or any applications that require searching. Searching is made easier by these algorithms. Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them.","post_status":"publish","comment_status":"open","ping_status":"open","post_password":"","post_name":"searching-algorithms-in-javascript","to_ping":"","pinged":"","post_modified":"2024-11-14 04:16:56","post_modified_gmt":"2024-11-14 04:16:56","post_content_filtered":"","post_parent":0,"guid":"https:\/\/blogue.tech\/?p=277","menu_order":0,"post_type":"post","post_mime_type":"","comment_count":"0","filter":"raw"}],"next":false,"prev":false,"total_page":1},"paged":1,"column_class":"jeg_col_3o3","class":"jnews_block_3"};
\nIf you complete the inner loop and find a match, increment the count of matches.<\/li>\n\n\n\n Return the count<\/li>\n<\/ul>\n\n\n\n function naiveSearch(str, word){\n var count = 0;\n for(var i = 0; i < str.length; i++){\n for(var j = 0; j < word.length; j++){\n if(word[j] !== str[i+j]) break;\n if(j === word.length - 1) count++;\n }\n }\n return count;\n}\n\n\nconsole.log(naiveSearch(\"search and find\", \"an\"))\n\noutput: [7]\n<\/pre>\n\n\n\nBut this way we have to search each and every word from the begining in case of multiple data to search.The Knuth-Morris-Pratt string search algorithm<\/a> or KMP algorithm is an algorithm for finding a substring within another string that uses information calculated about the substring to speed up the search process.Before looking through the text to be searched, a table of jump lengths is calculated from the search string. Rather than iterating through the whole string, you can determine how many characters to skip over based on the structure of the word being searched for. As you scan through the search text and you find a mismatch, you can start comparing characters again from the last matching substring between the search term and the search text.E.g. if you are searching through \"Hello world how ya doin?\" for the words \u201cold world new\u201d, every time you find an instance of \u201dold world new\u201d that isn\u2019t followed by a line-break, you can skip the characters of checking the string and restart from the beginning of your words, because you know that they can\u2019t occur again within that span because you have already checked those and they don\u2019t match the begging of the search words. Basically you already know that index is the next occurence of world, so you can start again from there.<\/p>\n\n\n\n
\/\/ Construct a table with table[i] as the length of the longest prefix of the substring 0..i\n\/\/ create a table of size equal to the length of `str`\n\/\/ table[i] will store the prefix of the longest prefix of the substring str[0..i]\n\/\/ the longest prefix of the substring str[0] has length\n\/\/ for the substrings the following substrings, we have two cases\n\/\/ case 1. the current character doesn't match the last character of the longest prefix\n\/\/ if that is the case, we have to backtrack, and try find a character that will be equal to the current character\n\/\/ if we reach 0, then we couldn't find a chracter\n\/\/ case 2. The last character of the longest prefix matches the current character in `str`\n\/\/ if that is the case, we know that the longest prefix at position i has one more character.\n\/\/ for example consider `.` be any character not contained in the set [a.c]\n\/\/ str = abc....abc\n\/\/ consider `i` to be the last character `c` in `str`\n\/\/ maxPrefix = will be 2 (the first `c` in `str`)\n\/\/ maxPrefix now will be 3\n\/\/ so the max prefix for table[9] is 3\nfunction makeTable(str) {\n \n \n var table = new Array(str.length);\n var maxPrefix = 0;\n \n table[0] = 0;\n \n \n for (var i = 1; i < str.length; i++) {\n while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) {\n \n maxPrefix = table[maxPrefix - 1];\n }\n \n if (str.charAt(maxPrefix) === str.charAt(i)) {\n maxPrefix++;\n }\n table[i] = maxPrefix;\n }\n return table;\n }\n \n\/\/ Find all the words that matches in a given string `str`\n\/\/ this algorithm is based on the Knuth\u2013Morris\u2013Pratt algorithm. Its beauty consists in that it performs the matching in O(n)\n\/\/ find the prefix table in O(n)\n\/\/ `j` is the index in `word(P)`\n\/\/ `i` is the index in `str(S)`\n\/\/ Case 1. S[i] == P[j] so we move to the next index in `S` and `P`\n\/\/ Case 2. `j` is equal to the length of `P`\n\/\/ that means that we reached the end of `P` and thus we found a match\n\/\/ Next we have to update `j` because we want to save some time\n\/\/ instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far.\n\/\/ j-1 means the last character of `P` because j is actually `P.length`\n\/\/ e.g.\n\/\/ S = a b a b d e\n\/\/ P = `a b`a b\n\/\/ we will jump to `a b` and we will compare d and a in the next iteration\n\/\/ a b a b `d` e\n\/\/ a b `a` b\n\/\/ Case 3.\n\/\/ S[i] != P[j] There's a mismatch!\n\/\/ if we have found at least a character in common, do the same thing as in case 2\n\/\/ otherwise, j = 0, and we can move to the next character S[i+1]function kmpMatching(str, word) {\n \n var prefixes = makeTable(word);\n var matches = [];\n \n \n var j = 0;\n var i = 0;\n while (i < str.length) {\n \n if (str.charAt(i) === word.charAt(j)) {\n i++;\n j++;\n }\n \n if (j === word.length) {\n matches.push(i-j);\n \n j = prefixes[j-1];\n }\n \n else if (str.charAt(i) !== word.charAt(j)) {\n \n if (j !== 0) {\n j = prefixes[j-1];\n } else {\n \n i++;\n }\n }\n }\n \n return matches;\n }\n\nconsole.log(kmpMatching(\"it implies that it is very important\",\"impo\"))\n\noutput: [27]\n<\/pre>\n\n\n\nWe can implement these algorithms in real world applications.Hope it helps.There are many other algorithms to use. But for a start these might help.<\/p>\n\n\n\n
Happy coding.....<\/p>\n","post_title":"Searching Algorithms in JavaScript","post_excerpt":"The Searching Algorithm can be implemented with other languages as well. But here we will work with JavaScript to solve the Searching Algorithms. These algorithms are used to handle or work with the search related task in our projects or any applications that require searching. Searching is made easier by these algorithms. Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them.","post_status":"publish","comment_status":"open","ping_status":"open","post_password":"","post_name":"searching-algorithms-in-javascript","to_ping":"","pinged":"","post_modified":"2024-11-14 04:16:56","post_modified_gmt":"2024-11-14 04:16:56","post_content_filtered":"","post_parent":0,"guid":"https:\/\/blogue.tech\/?p=277","menu_order":0,"post_type":"post","post_mime_type":"","comment_count":"0","filter":"raw"}],"next":false,"prev":false,"total_page":1},"paged":1,"column_class":"jeg_col_3o3","class":"jnews_block_3"};
\nIf the characters match,Keep going.<\/li>\n\n\n\n If you complete the inner loop and find a match, increment the count of matches.<\/li>\n\n\n\n Return the count<\/li>\n<\/ul>\n\n\n\n function naiveSearch(str, word){\n var count = 0;\n for(var i = 0; i < str.length; i++){\n for(var j = 0; j < word.length; j++){\n if(word[j] !== str[i+j]) break;\n if(j === word.length - 1) count++;\n }\n }\n return count;\n}\n\n\nconsole.log(naiveSearch(\"search and find\", \"an\"))\n\noutput: [7]\n<\/pre>\n\n\n\nBut this way we have to search each and every word from the begining in case of multiple data to search.The Knuth-Morris-Pratt string search algorithm<\/a> or KMP algorithm is an algorithm for finding a substring within another string that uses information calculated about the substring to speed up the search process.Before looking through the text to be searched, a table of jump lengths is calculated from the search string. Rather than iterating through the whole string, you can determine how many characters to skip over based on the structure of the word being searched for. As you scan through the search text and you find a mismatch, you can start comparing characters again from the last matching substring between the search term and the search text.E.g. if you are searching through \"Hello world how ya doin?\" for the words \u201cold world new\u201d, every time you find an instance of \u201dold world new\u201d that isn\u2019t followed by a line-break, you can skip the characters of checking the string and restart from the beginning of your words, because you know that they can\u2019t occur again within that span because you have already checked those and they don\u2019t match the begging of the search words. Basically you already know that index is the next occurence of world, so you can start again from there.<\/p>\n\n\n\n
\/\/ Construct a table with table[i] as the length of the longest prefix of the substring 0..i\n\/\/ create a table of size equal to the length of `str`\n\/\/ table[i] will store the prefix of the longest prefix of the substring str[0..i]\n\/\/ the longest prefix of the substring str[0] has length\n\/\/ for the substrings the following substrings, we have two cases\n\/\/ case 1. the current character doesn't match the last character of the longest prefix\n\/\/ if that is the case, we have to backtrack, and try find a character that will be equal to the current character\n\/\/ if we reach 0, then we couldn't find a chracter\n\/\/ case 2. The last character of the longest prefix matches the current character in `str`\n\/\/ if that is the case, we know that the longest prefix at position i has one more character.\n\/\/ for example consider `.` be any character not contained in the set [a.c]\n\/\/ str = abc....abc\n\/\/ consider `i` to be the last character `c` in `str`\n\/\/ maxPrefix = will be 2 (the first `c` in `str`)\n\/\/ maxPrefix now will be 3\n\/\/ so the max prefix for table[9] is 3\nfunction makeTable(str) {\n \n \n var table = new Array(str.length);\n var maxPrefix = 0;\n \n table[0] = 0;\n \n \n for (var i = 1; i < str.length; i++) {\n while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) {\n \n maxPrefix = table[maxPrefix - 1];\n }\n \n if (str.charAt(maxPrefix) === str.charAt(i)) {\n maxPrefix++;\n }\n table[i] = maxPrefix;\n }\n return table;\n }\n \n\/\/ Find all the words that matches in a given string `str`\n\/\/ this algorithm is based on the Knuth\u2013Morris\u2013Pratt algorithm. Its beauty consists in that it performs the matching in O(n)\n\/\/ find the prefix table in O(n)\n\/\/ `j` is the index in `word(P)`\n\/\/ `i` is the index in `str(S)`\n\/\/ Case 1. S[i] == P[j] so we move to the next index in `S` and `P`\n\/\/ Case 2. `j` is equal to the length of `P`\n\/\/ that means that we reached the end of `P` and thus we found a match\n\/\/ Next we have to update `j` because we want to save some time\n\/\/ instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far.\n\/\/ j-1 means the last character of `P` because j is actually `P.length`\n\/\/ e.g.\n\/\/ S = a b a b d e\n\/\/ P = `a b`a b\n\/\/ we will jump to `a b` and we will compare d and a in the next iteration\n\/\/ a b a b `d` e\n\/\/ a b `a` b\n\/\/ Case 3.\n\/\/ S[i] != P[j] There's a mismatch!\n\/\/ if we have found at least a character in common, do the same thing as in case 2\n\/\/ otherwise, j = 0, and we can move to the next character S[i+1]function kmpMatching(str, word) {\n \n var prefixes = makeTable(word);\n var matches = [];\n \n \n var j = 0;\n var i = 0;\n while (i < str.length) {\n \n if (str.charAt(i) === word.charAt(j)) {\n i++;\n j++;\n }\n \n if (j === word.length) {\n matches.push(i-j);\n \n j = prefixes[j-1];\n }\n \n else if (str.charAt(i) !== word.charAt(j)) {\n \n if (j !== 0) {\n j = prefixes[j-1];\n } else {\n \n i++;\n }\n }\n }\n \n return matches;\n }\n\nconsole.log(kmpMatching(\"it implies that it is very important\",\"impo\"))\n\noutput: [27]\n<\/pre>\n\n\n\nWe can implement these algorithms in real world applications.Hope it helps.There are many other algorithms to use. But for a start these might help.<\/p>\n\n\n\n
Happy coding.....<\/p>\n","post_title":"Searching Algorithms in JavaScript","post_excerpt":"The Searching Algorithm can be implemented with other languages as well. But here we will work with JavaScript to solve the Searching Algorithms. These algorithms are used to handle or work with the search related task in our projects or any applications that require searching. Searching is made easier by these algorithms. Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them.","post_status":"publish","comment_status":"open","ping_status":"open","post_password":"","post_name":"searching-algorithms-in-javascript","to_ping":"","pinged":"","post_modified":"2024-11-14 04:16:56","post_modified_gmt":"2024-11-14 04:16:56","post_content_filtered":"","post_parent":0,"guid":"https:\/\/blogue.tech\/?p=277","menu_order":0,"post_type":"post","post_mime_type":"","comment_count":"0","filter":"raw"}],"next":false,"prev":false,"total_page":1},"paged":1,"column_class":"jeg_col_3o3","class":"jnews_block_3"};
\nIf the characters don't match,break out of the inner loop.<\/li>\n\n\n\n If the characters match,Keep going.<\/li>\n\n\n\n If you complete the inner loop and find a match, increment the count of matches.<\/li>\n\n\n\n Return the count<\/li>\n<\/ul>\n\n\n\n function naiveSearch(str, word){\n var count = 0;\n for(var i = 0; i < str.length; i++){\n for(var j = 0; j < word.length; j++){\n if(word[j] !== str[i+j]) break;\n if(j === word.length - 1) count++;\n }\n }\n return count;\n}\n\n\nconsole.log(naiveSearch(\"search and find\", \"an\"))\n\noutput: [7]\n<\/pre>\n\n\n\nBut this way we have to search each and every word from the begining in case of multiple data to search.The Knuth-Morris-Pratt string search algorithm<\/a> or KMP algorithm is an algorithm for finding a substring within another string that uses information calculated about the substring to speed up the search process.Before looking through the text to be searched, a table of jump lengths is calculated from the search string. Rather than iterating through the whole string, you can determine how many characters to skip over based on the structure of the word being searched for. As you scan through the search text and you find a mismatch, you can start comparing characters again from the last matching substring between the search term and the search text.E.g. if you are searching through \"Hello world how ya doin?\" for the words \u201cold world new\u201d, every time you find an instance of \u201dold world new\u201d that isn\u2019t followed by a line-break, you can skip the characters of checking the string and restart from the beginning of your words, because you know that they can\u2019t occur again within that span because you have already checked those and they don\u2019t match the begging of the search words. Basically you already know that index is the next occurence of world, so you can start again from there.<\/p>\n\n\n\n
\/\/ Construct a table with table[i] as the length of the longest prefix of the substring 0..i\n\/\/ create a table of size equal to the length of `str`\n\/\/ table[i] will store the prefix of the longest prefix of the substring str[0..i]\n\/\/ the longest prefix of the substring str[0] has length\n\/\/ for the substrings the following substrings, we have two cases\n\/\/ case 1. the current character doesn't match the last character of the longest prefix\n\/\/ if that is the case, we have to backtrack, and try find a character that will be equal to the current character\n\/\/ if we reach 0, then we couldn't find a chracter\n\/\/ case 2. The last character of the longest prefix matches the current character in `str`\n\/\/ if that is the case, we know that the longest prefix at position i has one more character.\n\/\/ for example consider `.` be any character not contained in the set [a.c]\n\/\/ str = abc....abc\n\/\/ consider `i` to be the last character `c` in `str`\n\/\/ maxPrefix = will be 2 (the first `c` in `str`)\n\/\/ maxPrefix now will be 3\n\/\/ so the max prefix for table[9] is 3\nfunction makeTable(str) {\n \n \n var table = new Array(str.length);\n var maxPrefix = 0;\n \n table[0] = 0;\n \n \n for (var i = 1; i < str.length; i++) {\n while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) {\n \n maxPrefix = table[maxPrefix - 1];\n }\n \n if (str.charAt(maxPrefix) === str.charAt(i)) {\n maxPrefix++;\n }\n table[i] = maxPrefix;\n }\n return table;\n }\n \n\/\/ Find all the words that matches in a given string `str`\n\/\/ this algorithm is based on the Knuth\u2013Morris\u2013Pratt algorithm. Its beauty consists in that it performs the matching in O(n)\n\/\/ find the prefix table in O(n)\n\/\/ `j` is the index in `word(P)`\n\/\/ `i` is the index in `str(S)`\n\/\/ Case 1. S[i] == P[j] so we move to the next index in `S` and `P`\n\/\/ Case 2. `j` is equal to the length of `P`\n\/\/ that means that we reached the end of `P` and thus we found a match\n\/\/ Next we have to update `j` because we want to save some time\n\/\/ instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far.\n\/\/ j-1 means the last character of `P` because j is actually `P.length`\n\/\/ e.g.\n\/\/ S = a b a b d e\n\/\/ P = `a b`a b\n\/\/ we will jump to `a b` and we will compare d and a in the next iteration\n\/\/ a b a b `d` e\n\/\/ a b `a` b\n\/\/ Case 3.\n\/\/ S[i] != P[j] There's a mismatch!\n\/\/ if we have found at least a character in common, do the same thing as in case 2\n\/\/ otherwise, j = 0, and we can move to the next character S[i+1]function kmpMatching(str, word) {\n \n var prefixes = makeTable(word);\n var matches = [];\n \n \n var j = 0;\n var i = 0;\n while (i < str.length) {\n \n if (str.charAt(i) === word.charAt(j)) {\n i++;\n j++;\n }\n \n if (j === word.length) {\n matches.push(i-j);\n \n j = prefixes[j-1];\n }\n \n else if (str.charAt(i) !== word.charAt(j)) {\n \n if (j !== 0) {\n j = prefixes[j-1];\n } else {\n \n i++;\n }\n }\n }\n \n return matches;\n }\n\nconsole.log(kmpMatching(\"it implies that it is very important\",\"impo\"))\n\noutput: [27]\n<\/pre>\n\n\n\nWe can implement these algorithms in real world applications.Hope it helps.There are many other algorithms to use. But for a start these might help.<\/p>\n\n\n\n
Happy coding.....<\/p>\n","post_title":"Searching Algorithms in JavaScript","post_excerpt":"The Searching Algorithm can be implemented with other languages as well. But here we will work with JavaScript to solve the Searching Algorithms. These algorithms are used to handle or work with the search related task in our projects or any applications that require searching. Searching is made easier by these algorithms. Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them.","post_status":"publish","comment_status":"open","ping_status":"open","post_password":"","post_name":"searching-algorithms-in-javascript","to_ping":"","pinged":"","post_modified":"2024-11-14 04:16:56","post_modified_gmt":"2024-11-14 04:16:56","post_content_filtered":"","post_parent":0,"guid":"https:\/\/blogue.tech\/?p=277","menu_order":0,"post_type":"post","post_mime_type":"","comment_count":"0","filter":"raw"}],"next":false,"prev":false,"total_page":1},"paged":1,"column_class":"jeg_col_3o3","class":"jnews_block_3"};
\nLoop Over the shorter string.<\/li>\n\n\n\n If the characters don't match,break out of the inner loop.<\/li>\n\n\n\n If the characters match,Keep going.<\/li>\n\n\n\n If you complete the inner loop and find a match, increment the count of matches.<\/li>\n\n\n\n Return the count<\/li>\n<\/ul>\n\n\n\n function naiveSearch(str, word){\n var count = 0;\n for(var i = 0; i < str.length; i++){\n for(var j = 0; j < word.length; j++){\n if(word[j] !== str[i+j]) break;\n if(j === word.length - 1) count++;\n }\n }\n return count;\n}\n\n\nconsole.log(naiveSearch(\"search and find\", \"an\"))\n\noutput: [7]\n<\/pre>\n\n\n\nBut this way we have to search each and every word from the begining in case of multiple data to search.The Knuth-Morris-Pratt string search algorithm<\/a> or KMP algorithm is an algorithm for finding a substring within another string that uses information calculated about the substring to speed up the search process.Before looking through the text to be searched, a table of jump lengths is calculated from the search string. Rather than iterating through the whole string, you can determine how many characters to skip over based on the structure of the word being searched for. As you scan through the search text and you find a mismatch, you can start comparing characters again from the last matching substring between the search term and the search text.E.g. if you are searching through \"Hello world how ya doin?\" for the words \u201cold world new\u201d, every time you find an instance of \u201dold world new\u201d that isn\u2019t followed by a line-break, you can skip the characters of checking the string and restart from the beginning of your words, because you know that they can\u2019t occur again within that span because you have already checked those and they don\u2019t match the begging of the search words. Basically you already know that index is the next occurence of world, so you can start again from there.<\/p>\n\n\n\n
\/\/ Construct a table with table[i] as the length of the longest prefix of the substring 0..i\n\/\/ create a table of size equal to the length of `str`\n\/\/ table[i] will store the prefix of the longest prefix of the substring str[0..i]\n\/\/ the longest prefix of the substring str[0] has length\n\/\/ for the substrings the following substrings, we have two cases\n\/\/ case 1. the current character doesn't match the last character of the longest prefix\n\/\/ if that is the case, we have to backtrack, and try find a character that will be equal to the current character\n\/\/ if we reach 0, then we couldn't find a chracter\n\/\/ case 2. The last character of the longest prefix matches the current character in `str`\n\/\/ if that is the case, we know that the longest prefix at position i has one more character.\n\/\/ for example consider `.` be any character not contained in the set [a.c]\n\/\/ str = abc....abc\n\/\/ consider `i` to be the last character `c` in `str`\n\/\/ maxPrefix = will be 2 (the first `c` in `str`)\n\/\/ maxPrefix now will be 3\n\/\/ so the max prefix for table[9] is 3\nfunction makeTable(str) {\n \n \n var table = new Array(str.length);\n var maxPrefix = 0;\n \n table[0] = 0;\n \n \n for (var i = 1; i < str.length; i++) {\n while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) {\n \n maxPrefix = table[maxPrefix - 1];\n }\n \n if (str.charAt(maxPrefix) === str.charAt(i)) {\n maxPrefix++;\n }\n table[i] = maxPrefix;\n }\n return table;\n }\n \n\/\/ Find all the words that matches in a given string `str`\n\/\/ this algorithm is based on the Knuth\u2013Morris\u2013Pratt algorithm. Its beauty consists in that it performs the matching in O(n)\n\/\/ find the prefix table in O(n)\n\/\/ `j` is the index in `word(P)`\n\/\/ `i` is the index in `str(S)`\n\/\/ Case 1. S[i] == P[j] so we move to the next index in `S` and `P`\n\/\/ Case 2. `j` is equal to the length of `P`\n\/\/ that means that we reached the end of `P` and thus we found a match\n\/\/ Next we have to update `j` because we want to save some time\n\/\/ instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far.\n\/\/ j-1 means the last character of `P` because j is actually `P.length`\n\/\/ e.g.\n\/\/ S = a b a b d e\n\/\/ P = `a b`a b\n\/\/ we will jump to `a b` and we will compare d and a in the next iteration\n\/\/ a b a b `d` e\n\/\/ a b `a` b\n\/\/ Case 3.\n\/\/ S[i] != P[j] There's a mismatch!\n\/\/ if we have found at least a character in common, do the same thing as in case 2\n\/\/ otherwise, j = 0, and we can move to the next character S[i+1]function kmpMatching(str, word) {\n \n var prefixes = makeTable(word);\n var matches = [];\n \n \n var j = 0;\n var i = 0;\n while (i < str.length) {\n \n if (str.charAt(i) === word.charAt(j)) {\n i++;\n j++;\n }\n \n if (j === word.length) {\n matches.push(i-j);\n \n j = prefixes[j-1];\n }\n \n else if (str.charAt(i) !== word.charAt(j)) {\n \n if (j !== 0) {\n j = prefixes[j-1];\n } else {\n \n i++;\n }\n }\n }\n \n return matches;\n }\n\nconsole.log(kmpMatching(\"it implies that it is very important\",\"impo\"))\n\noutput: [27]\n<\/pre>\n\n\n\nWe can implement these algorithms in real world applications.Hope it helps.There are many other algorithms to use. But for a start these might help.<\/p>\n\n\n\n
Happy coding.....<\/p>\n","post_title":"Searching Algorithms in JavaScript","post_excerpt":"The Searching Algorithm can be implemented with other languages as well. But here we will work with JavaScript to solve the Searching Algorithms. These algorithms are used to handle or work with the search related task in our projects or any applications that require searching. Searching is made easier by these algorithms. Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them.","post_status":"publish","comment_status":"open","ping_status":"open","post_password":"","post_name":"searching-algorithms-in-javascript","to_ping":"","pinged":"","post_modified":"2024-11-14 04:16:56","post_modified_gmt":"2024-11-14 04:16:56","post_content_filtered":"","post_parent":0,"guid":"https:\/\/blogue.tech\/?p=277","menu_order":0,"post_type":"post","post_mime_type":"","comment_count":"0","filter":"raw"}],"next":false,"prev":false,"total_page":1},"paged":1,"column_class":"jeg_col_3o3","class":"jnews_block_3"};
\nLoop Over the longer string.<\/li>\n\n\n\n Loop Over the shorter string.<\/li>\n\n\n\n If the characters don't match,break out of the inner loop.<\/li>\n\n\n\n If the characters match,Keep going.<\/li>\n\n\n\n If you complete the inner loop and find a match, increment the count of matches.<\/li>\n\n\n\n Return the count<\/li>\n<\/ul>\n\n\n\n function naiveSearch(str, word){\n var count = 0;\n for(var i = 0; i < str.length; i++){\n for(var j = 0; j < word.length; j++){\n if(word[j] !== str[i+j]) break;\n if(j === word.length - 1) count++;\n }\n }\n return count;\n}\n\n\nconsole.log(naiveSearch(\"search and find\", \"an\"))\n\noutput: [7]\n<\/pre>\n\n\n\nBut this way we have to search each and every word from the begining in case of multiple data to search.The Knuth-Morris-Pratt string search algorithm<\/a> or KMP algorithm is an algorithm for finding a substring within another string that uses information calculated about the substring to speed up the search process.Before looking through the text to be searched, a table of jump lengths is calculated from the search string. Rather than iterating through the whole string, you can determine how many characters to skip over based on the structure of the word being searched for. As you scan through the search text and you find a mismatch, you can start comparing characters again from the last matching substring between the search term and the search text.E.g. if you are searching through \"Hello world how ya doin?\" for the words \u201cold world new\u201d, every time you find an instance of \u201dold world new\u201d that isn\u2019t followed by a line-break, you can skip the characters of checking the string and restart from the beginning of your words, because you know that they can\u2019t occur again within that span because you have already checked those and they don\u2019t match the begging of the search words. Basically you already know that index is the next occurence of world, so you can start again from there.<\/p>\n\n\n\n
\/\/ Construct a table with table[i] as the length of the longest prefix of the substring 0..i\n\/\/ create a table of size equal to the length of `str`\n\/\/ table[i] will store the prefix of the longest prefix of the substring str[0..i]\n\/\/ the longest prefix of the substring str[0] has length\n\/\/ for the substrings the following substrings, we have two cases\n\/\/ case 1. the current character doesn't match the last character of the longest prefix\n\/\/ if that is the case, we have to backtrack, and try find a character that will be equal to the current character\n\/\/ if we reach 0, then we couldn't find a chracter\n\/\/ case 2. The last character of the longest prefix matches the current character in `str`\n\/\/ if that is the case, we know that the longest prefix at position i has one more character.\n\/\/ for example consider `.` be any character not contained in the set [a.c]\n\/\/ str = abc....abc\n\/\/ consider `i` to be the last character `c` in `str`\n\/\/ maxPrefix = will be 2 (the first `c` in `str`)\n\/\/ maxPrefix now will be 3\n\/\/ so the max prefix for table[9] is 3\nfunction makeTable(str) {\n \n \n var table = new Array(str.length);\n var maxPrefix = 0;\n \n table[0] = 0;\n \n \n for (var i = 1; i < str.length; i++) {\n while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) {\n \n maxPrefix = table[maxPrefix - 1];\n }\n \n if (str.charAt(maxPrefix) === str.charAt(i)) {\n maxPrefix++;\n }\n table[i] = maxPrefix;\n }\n return table;\n }\n \n\/\/ Find all the words that matches in a given string `str`\n\/\/ this algorithm is based on the Knuth\u2013Morris\u2013Pratt algorithm. Its beauty consists in that it performs the matching in O(n)\n\/\/ find the prefix table in O(n)\n\/\/ `j` is the index in `word(P)`\n\/\/ `i` is the index in `str(S)`\n\/\/ Case 1. S[i] == P[j] so we move to the next index in `S` and `P`\n\/\/ Case 2. `j` is equal to the length of `P`\n\/\/ that means that we reached the end of `P` and thus we found a match\n\/\/ Next we have to update `j` because we want to save some time\n\/\/ instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far.\n\/\/ j-1 means the last character of `P` because j is actually `P.length`\n\/\/ e.g.\n\/\/ S = a b a b d e\n\/\/ P = `a b`a b\n\/\/ we will jump to `a b` and we will compare d and a in the next iteration\n\/\/ a b a b `d` e\n\/\/ a b `a` b\n\/\/ Case 3.\n\/\/ S[i] != P[j] There's a mismatch!\n\/\/ if we have found at least a character in common, do the same thing as in case 2\n\/\/ otherwise, j = 0, and we can move to the next character S[i+1]function kmpMatching(str, word) {\n \n var prefixes = makeTable(word);\n var matches = [];\n \n \n var j = 0;\n var i = 0;\n while (i < str.length) {\n \n if (str.charAt(i) === word.charAt(j)) {\n i++;\n j++;\n }\n \n if (j === word.length) {\n matches.push(i-j);\n \n j = prefixes[j-1];\n }\n \n else if (str.charAt(i) !== word.charAt(j)) {\n \n if (j !== 0) {\n j = prefixes[j-1];\n } else {\n \n i++;\n }\n }\n }\n \n return matches;\n }\n\nconsole.log(kmpMatching(\"it implies that it is very important\",\"impo\"))\n\noutput: [27]\n<\/pre>\n\n\n\nWe can implement these algorithms in real world applications.Hope it helps.There are many other algorithms to use. But for a start these might help.<\/p>\n\n\n\n
Happy coding.....<\/p>\n","post_title":"Searching Algorithms in JavaScript","post_excerpt":"The Searching Algorithm can be implemented with other languages as well. But here we will work with JavaScript to solve the Searching Algorithms. These algorithms are used to handle or work with the search related task in our projects or any applications that require searching. Searching is made easier by these algorithms. Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them.","post_status":"publish","comment_status":"open","ping_status":"open","post_password":"","post_name":"searching-algorithms-in-javascript","to_ping":"","pinged":"","post_modified":"2024-11-14 04:16:56","post_modified_gmt":"2024-11-14 04:16:56","post_content_filtered":"","post_parent":0,"guid":"https:\/\/blogue.tech\/?p=277","menu_order":0,"post_type":"post","post_mime_type":"","comment_count":"0","filter":"raw"}],"next":false,"prev":false,"total_page":1},"paged":1,"column_class":"jeg_col_3o3","class":"jnews_block_3"};
\n\n
- Loop Over the longer string.<\/li>\n\n\n\n
- Loop Over the shorter string.<\/li>\n\n\n\n
- If the characters don't match,break out of the inner loop.<\/li>\n\n\n\n
- If the characters match,Keep going.<\/li>\n\n\n\n
- If you complete the inner loop and find a match, increment the count of matches.<\/li>\n\n\n\n
- Return the count<\/li>\n<\/ul>\n\n\n\n
function naiveSearch(str, word){\n var count = 0;\n for(var i = 0; i < str.length; i++){\n for(var j = 0; j < word.length; j++){\n if(word[j] !== str[i+j]) break;\n if(j === word.length - 1) count++;\n }\n }\n return count;\n}\n\n\nconsole.log(naiveSearch(\"search and find\", \"an\"))\n\noutput: [7]\n<\/pre>\n\n\n\nBut this way we have to search each and every word from the begining in case of multiple data to search.The Knuth-Morris-Pratt string search algorithm<\/a> or KMP algorithm is an algorithm for finding a substring within another string that uses information calculated about the substring to speed up the search process.Before looking through the text to be searched, a table of jump lengths is calculated from the search string. Rather than iterating through the whole string, you can determine how many characters to skip over based on the structure of the word being searched for. As you scan through the search text and you find a mismatch, you can start comparing characters again from the last matching substring between the search term and the search text.E.g. if you are searching through \"Hello world how ya doin?\" for the words \u201cold world new\u201d, every time you find an instance of \u201dold world new\u201d that isn\u2019t followed by a line-break, you can skip the characters of checking the string and restart from the beginning of your words, because you know that they can\u2019t occur again within that span because you have already checked those and they don\u2019t match the begging of the search words. Basically you already know that index is the next occurence of world, so you can start again from there.<\/p>\n\n\n\n
\/\/ Construct a table with table[i] as the length of the longest prefix of the substring 0..i\n\/\/ create a table of size equal to the length of `str`\n\/\/ table[i] will store the prefix of the longest prefix of the substring str[0..i]\n\/\/ the longest prefix of the substring str[0] has length\n\/\/ for the substrings the following substrings, we have two cases\n\/\/ case 1. the current character doesn't match the last character of the longest prefix\n\/\/ if that is the case, we have to backtrack, and try find a character that will be equal to the current character\n\/\/ if we reach 0, then we couldn't find a chracter\n\/\/ case 2. The last character of the longest prefix matches the current character in `str`\n\/\/ if that is the case, we know that the longest prefix at position i has one more character.\n\/\/ for example consider `.` be any character not contained in the set [a.c]\n\/\/ str = abc....abc\n\/\/ consider `i` to be the last character `c` in `str`\n\/\/ maxPrefix = will be 2 (the first `c` in `str`)\n\/\/ maxPrefix now will be 3\n\/\/ so the max prefix for table[9] is 3\nfunction makeTable(str) {\n \n \n var table = new Array(str.length);\n var maxPrefix = 0;\n \n table[0] = 0;\n \n \n for (var i = 1; i < str.length; i++) {\n while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) {\n \n maxPrefix = table[maxPrefix - 1];\n }\n \n if (str.charAt(maxPrefix) === str.charAt(i)) {\n maxPrefix++;\n }\n table[i] = maxPrefix;\n }\n return table;\n }\n \n\/\/ Find all the words that matches in a given string `str`\n\/\/ this algorithm is based on the Knuth\u2013Morris\u2013Pratt algorithm. Its beauty consists in that it performs the matching in O(n)\n\/\/ find the prefix table in O(n)\n\/\/ `j` is the index in `word(P)`\n\/\/ `i` is the index in `str(S)`\n\/\/ Case 1. S[i] == P[j] so we move to the next index in `S` and `P`\n\/\/ Case 2. `j` is equal to the length of `P`\n\/\/ that means that we reached the end of `P` and thus we found a match\n\/\/ Next we have to update `j` because we want to save some time\n\/\/ instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far.\n\/\/ j-1 means the last character of `P` because j is actually `P.length`\n\/\/ e.g.\n\/\/ S = a b a b d e\n\/\/ P = `a b`a b\n\/\/ we will jump to `a b` and we will compare d and a in the next iteration\n\/\/ a b a b `d` e\n\/\/ a b `a` b\n\/\/ Case 3.\n\/\/ S[i] != P[j] There's a mismatch!\n\/\/ if we have found at least a character in common, do the same thing as in case 2\n\/\/ otherwise, j = 0, and we can move to the next character S[i+1]function kmpMatching(str, word) {\n \n var prefixes = makeTable(word);\n var matches = [];\n \n \n var j = 0;\n var i = 0;\n while (i < str.length) {\n \n if (str.charAt(i) === word.charAt(j)) {\n i++;\n j++;\n }\n \n if (j === word.length) {\n matches.push(i-j);\n \n j = prefixes[j-1];\n }\n \n else if (str.charAt(i) !== word.charAt(j)) {\n \n if (j !== 0) {\n j = prefixes[j-1];\n } else {\n \n i++;\n }\n }\n }\n \n return matches;\n }\n\nconsole.log(kmpMatching(\"it implies that it is very important\",\"impo\"))\n\noutput: [27]\n<\/pre>\n\n\n\nWe can implement these algorithms in real world applications.Hope it helps.There are many other algorithms to use. But for a start these might help.<\/p>\n\n\n\n
Happy coding.....<\/p>\n","post_title":"Searching Algorithms in JavaScript","post_excerpt":"The Searching Algorithm can be implemented with other languages as well. But here we will work with JavaScript to solve the Searching Algorithms. These algorithms are used to handle or work with the search related task in our projects or any applications that require searching. Searching is made easier by these algorithms. Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them.","post_status":"publish","comment_status":"open","ping_status":"open","post_password":"","post_name":"searching-algorithms-in-javascript","to_ping":"","pinged":"","post_modified":"2024-11-14 04:16:56","post_modified_gmt":"2024-11-14 04:16:56","post_content_filtered":"","post_parent":0,"guid":"https:\/\/blogue.tech\/?p=277","menu_order":0,"post_type":"post","post_mime_type":"","comment_count":"0","filter":"raw"}],"next":false,"prev":false,"total_page":1},"paged":1,"column_class":"jeg_col_3o3","class":"jnews_block_3"};
\nPseudocode:<\/u><\/strong><\/p>\n\n\n\n
\n
- Loop Over the longer string.<\/li>\n\n\n\n
- Loop Over the shorter string.<\/li>\n\n\n\n
- If the characters don't match,break out of the inner loop.<\/li>\n\n\n\n
- If the characters match,Keep going.<\/li>\n\n\n\n
- If you complete the inner loop and find a match, increment the count of matches.<\/li>\n\n\n\n
- Return the count<\/li>\n<\/ul>\n\n\n\n
function naiveSearch(str, word){\n var count = 0;\n for(var i = 0; i < str.length; i++){\n for(var j = 0; j < word.length; j++){\n if(word[j] !== str[i+j]) break;\n if(j === word.length - 1) count++;\n }\n }\n return count;\n}\n\n\nconsole.log(naiveSearch(\"search and find\", \"an\"))\n\noutput: [7]\n<\/pre>\n\n\n\nBut this way we have to search each and every word from the begining in case of multiple data to search.The Knuth-Morris-Pratt string search algorithm<\/a> or KMP algorithm is an algorithm for finding a substring within another string that uses information calculated about the substring to speed up the search process.Before looking through the text to be searched, a table of jump lengths is calculated from the search string. Rather than iterating through the whole string, you can determine how many characters to skip over based on the structure of the word being searched for. As you scan through the search text and you find a mismatch, you can start comparing characters again from the last matching substring between the search term and the search text.E.g. if you are searching through \"Hello world how ya doin?\" for the words \u201cold world new\u201d, every time you find an instance of \u201dold world new\u201d that isn\u2019t followed by a line-break, you can skip the characters of checking the string and restart from the beginning of your words, because you know that they can\u2019t occur again within that span because you have already checked those and they don\u2019t match the begging of the search words. Basically you already know that index is the next occurence of world, so you can start again from there.<\/p>\n\n\n\n
\/\/ Construct a table with table[i] as the length of the longest prefix of the substring 0..i\n\/\/ create a table of size equal to the length of `str`\n\/\/ table[i] will store the prefix of the longest prefix of the substring str[0..i]\n\/\/ the longest prefix of the substring str[0] has length\n\/\/ for the substrings the following substrings, we have two cases\n\/\/ case 1. the current character doesn't match the last character of the longest prefix\n\/\/ if that is the case, we have to backtrack, and try find a character that will be equal to the current character\n\/\/ if we reach 0, then we couldn't find a chracter\n\/\/ case 2. The last character of the longest prefix matches the current character in `str`\n\/\/ if that is the case, we know that the longest prefix at position i has one more character.\n\/\/ for example consider `.` be any character not contained in the set [a.c]\n\/\/ str = abc....abc\n\/\/ consider `i` to be the last character `c` in `str`\n\/\/ maxPrefix = will be 2 (the first `c` in `str`)\n\/\/ maxPrefix now will be 3\n\/\/ so the max prefix for table[9] is 3\nfunction makeTable(str) {\n \n \n var table = new Array(str.length);\n var maxPrefix = 0;\n \n table[0] = 0;\n \n \n for (var i = 1; i < str.length; i++) {\n while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) {\n \n maxPrefix = table[maxPrefix - 1];\n }\n \n if (str.charAt(maxPrefix) === str.charAt(i)) {\n maxPrefix++;\n }\n table[i] = maxPrefix;\n }\n return table;\n }\n \n\/\/ Find all the words that matches in a given string `str`\n\/\/ this algorithm is based on the Knuth\u2013Morris\u2013Pratt algorithm. Its beauty consists in that it performs the matching in O(n)\n\/\/ find the prefix table in O(n)\n\/\/ `j` is the index in `word(P)`\n\/\/ `i` is the index in `str(S)`\n\/\/ Case 1. S[i] == P[j] so we move to the next index in `S` and `P`\n\/\/ Case 2. `j` is equal to the length of `P`\n\/\/ that means that we reached the end of `P` and thus we found a match\n\/\/ Next we have to update `j` because we want to save some time\n\/\/ instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far.\n\/\/ j-1 means the last character of `P` because j is actually `P.length`\n\/\/ e.g.\n\/\/ S = a b a b d e\n\/\/ P = `a b`a b\n\/\/ we will jump to `a b` and we will compare d and a in the next iteration\n\/\/ a b a b `d` e\n\/\/ a b `a` b\n\/\/ Case 3.\n\/\/ S[i] != P[j] There's a mismatch!\n\/\/ if we have found at least a character in common, do the same thing as in case 2\n\/\/ otherwise, j = 0, and we can move to the next character S[i+1]function kmpMatching(str, word) {\n \n var prefixes = makeTable(word);\n var matches = [];\n \n \n var j = 0;\n var i = 0;\n while (i < str.length) {\n \n if (str.charAt(i) === word.charAt(j)) {\n i++;\n j++;\n }\n \n if (j === word.length) {\n matches.push(i-j);\n \n j = prefixes[j-1];\n }\n \n else if (str.charAt(i) !== word.charAt(j)) {\n \n if (j !== 0) {\n j = prefixes[j-1];\n } else {\n \n i++;\n }\n }\n }\n \n return matches;\n }\n\nconsole.log(kmpMatching(\"it implies that it is very important\",\"impo\"))\n\noutput: [27]\n<\/pre>\n\n\n\nWe can implement these algorithms in real world applications.Hope it helps.There are many other algorithms to use. But for a start these might help.<\/p>\n\n\n\n
Happy coding.....<\/p>\n","post_title":"Searching Algorithms in JavaScript","post_excerpt":"The Searching Algorithm can be implemented with other languages as well. But here we will work with JavaScript to solve the Searching Algorithms. These algorithms are used to handle or work with the search related task in our projects or any applications that require searching. Searching is made easier by these algorithms. Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them.","post_status":"publish","comment_status":"open","ping_status":"open","post_password":"","post_name":"searching-algorithms-in-javascript","to_ping":"","pinged":"","post_modified":"2024-11-14 04:16:56","post_modified_gmt":"2024-11-14 04:16:56","post_content_filtered":"","post_parent":0,"guid":"https:\/\/blogue.tech\/?p=277","menu_order":0,"post_type":"post","post_mime_type":"","comment_count":"0","filter":"raw"}],"next":false,"prev":false,"total_page":1},"paged":1,"column_class":"jeg_col_3o3","class":"jnews_block_3"};
\nThis not totally related to linear search or Binary search. I just wanted to add it here as it is very much important for searching string. A very simple way to search strings is given below:<\/p>\n\n\n\n
Pseudocode:<\/u><\/strong><\/p>\n\n\n\n
\n
- Loop Over the longer string.<\/li>\n\n\n\n
- Loop Over the shorter string.<\/li>\n\n\n\n
- If the characters don't match,break out of the inner loop.<\/li>\n\n\n\n
- If the characters match,Keep going.<\/li>\n\n\n\n
- If you complete the inner loop and find a match, increment the count of matches.<\/li>\n\n\n\n
- Return the count<\/li>\n<\/ul>\n\n\n\n
function naiveSearch(str, word){\n var count = 0;\n for(var i = 0; i < str.length; i++){\n for(var j = 0; j < word.length; j++){\n if(word[j] !== str[i+j]) break;\n if(j === word.length - 1) count++;\n }\n }\n return count;\n}\n\n\nconsole.log(naiveSearch(\"search and find\", \"an\"))\n\noutput: [7]\n<\/pre>\n\n\n\nBut this way we have to search each and every word from the begining in case of multiple data to search.The Knuth-Morris-Pratt string search algorithm<\/a> or KMP algorithm is an algorithm for finding a substring within another string that uses information calculated about the substring to speed up the search process.Before looking through the text to be searched, a table of jump lengths is calculated from the search string. Rather than iterating through the whole string, you can determine how many characters to skip over based on the structure of the word being searched for. As you scan through the search text and you find a mismatch, you can start comparing characters again from the last matching substring between the search term and the search text.E.g. if you are searching through \"Hello world how ya doin?\" for the words \u201cold world new\u201d, every time you find an instance of \u201dold world new\u201d that isn\u2019t followed by a line-break, you can skip the characters of checking the string and restart from the beginning of your words, because you know that they can\u2019t occur again within that span because you have already checked those and they don\u2019t match the begging of the search words. Basically you already know that index is the next occurence of world, so you can start again from there.<\/p>\n\n\n\n
\/\/ Construct a table with table[i] as the length of the longest prefix of the substring 0..i\n\/\/ create a table of size equal to the length of `str`\n\/\/ table[i] will store the prefix of the longest prefix of the substring str[0..i]\n\/\/ the longest prefix of the substring str[0] has length\n\/\/ for the substrings the following substrings, we have two cases\n\/\/ case 1. the current character doesn't match the last character of the longest prefix\n\/\/ if that is the case, we have to backtrack, and try find a character that will be equal to the current character\n\/\/ if we reach 0, then we couldn't find a chracter\n\/\/ case 2. The last character of the longest prefix matches the current character in `str`\n\/\/ if that is the case, we know that the longest prefix at position i has one more character.\n\/\/ for example consider `.` be any character not contained in the set [a.c]\n\/\/ str = abc....abc\n\/\/ consider `i` to be the last character `c` in `str`\n\/\/ maxPrefix = will be 2 (the first `c` in `str`)\n\/\/ maxPrefix now will be 3\n\/\/ so the max prefix for table[9] is 3\nfunction makeTable(str) {\n \n \n var table = new Array(str.length);\n var maxPrefix = 0;\n \n table[0] = 0;\n \n \n for (var i = 1; i < str.length; i++) {\n while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) {\n \n maxPrefix = table[maxPrefix - 1];\n }\n \n if (str.charAt(maxPrefix) === str.charAt(i)) {\n maxPrefix++;\n }\n table[i] = maxPrefix;\n }\n return table;\n }\n \n\/\/ Find all the words that matches in a given string `str`\n\/\/ this algorithm is based on the Knuth\u2013Morris\u2013Pratt algorithm. Its beauty consists in that it performs the matching in O(n)\n\/\/ find the prefix table in O(n)\n\/\/ `j` is the index in `word(P)`\n\/\/ `i` is the index in `str(S)`\n\/\/ Case 1. S[i] == P[j] so we move to the next index in `S` and `P`\n\/\/ Case 2. `j` is equal to the length of `P`\n\/\/ that means that we reached the end of `P` and thus we found a match\n\/\/ Next we have to update `j` because we want to save some time\n\/\/ instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far.\n\/\/ j-1 means the last character of `P` because j is actually `P.length`\n\/\/ e.g.\n\/\/ S = a b a b d e\n\/\/ P = `a b`a b\n\/\/ we will jump to `a b` and we will compare d and a in the next iteration\n\/\/ a b a b `d` e\n\/\/ a b `a` b\n\/\/ Case 3.\n\/\/ S[i] != P[j] There's a mismatch!\n\/\/ if we have found at least a character in common, do the same thing as in case 2\n\/\/ otherwise, j = 0, and we can move to the next character S[i+1]function kmpMatching(str, word) {\n \n var prefixes = makeTable(word);\n var matches = [];\n \n \n var j = 0;\n var i = 0;\n while (i < str.length) {\n \n if (str.charAt(i) === word.charAt(j)) {\n i++;\n j++;\n }\n \n if (j === word.length) {\n matches.push(i-j);\n \n j = prefixes[j-1];\n }\n \n else if (str.charAt(i) !== word.charAt(j)) {\n \n if (j !== 0) {\n j = prefixes[j-1];\n } else {\n \n i++;\n }\n }\n }\n \n return matches;\n }\n\nconsole.log(kmpMatching(\"it implies that it is very important\",\"impo\"))\n\noutput: [27]\n<\/pre>\n\n\n\nWe can implement these algorithms in real world applications.Hope it helps.There are many other algorithms to use. But for a start these might help.<\/p>\n\n\n\n
Happy coding.....<\/p>\n","post_title":"Searching Algorithms in JavaScript","post_excerpt":"The Searching Algorithm can be implemented with other languages as well. But here we will work with JavaScript to solve the Searching Algorithms. These algorithms are used to handle or work with the search related task in our projects or any applications that require searching. Searching is made easier by these algorithms. Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them.","post_status":"publish","comment_status":"open","ping_status":"open","post_password":"","post_name":"searching-algorithms-in-javascript","to_ping":"","pinged":"","post_modified":"2024-11-14 04:16:56","post_modified_gmt":"2024-11-14 04:16:56","post_content_filtered":"","post_parent":0,"guid":"https:\/\/blogue.tech\/?p=277","menu_order":0,"post_type":"post","post_mime_type":"","comment_count":"0","filter":"raw"}],"next":false,"prev":false,"total_page":1},"paged":1,"column_class":"jeg_col_3o3","class":"jnews_block_3"};
\n3.String Search<\/strong><\/h2>\n\n\n\n
This not totally related to linear search or Binary search. I just wanted to add it here as it is very much important for searching string. A very simple way to search strings is given below:<\/p>\n\n\n\n
Pseudocode:<\/u><\/strong><\/p>\n\n\n\n
\n
- Loop Over the longer string.<\/li>\n\n\n\n
- Loop Over the shorter string.<\/li>\n\n\n\n
- If the characters don't match,break out of the inner loop.<\/li>\n\n\n\n
- If the characters match,Keep going.<\/li>\n\n\n\n
- If you complete the inner loop and find a match, increment the count of matches.<\/li>\n\n\n\n
- Return the count<\/li>\n<\/ul>\n\n\n\n
function naiveSearch(str, word){\n var count = 0;\n for(var i = 0; i < str.length; i++){\n for(var j = 0; j < word.length; j++){\n if(word[j] !== str[i+j]) break;\n if(j === word.length - 1) count++;\n }\n }\n return count;\n}\n\n\nconsole.log(naiveSearch(\"search and find\", \"an\"))\n\noutput: [7]\n<\/pre>\n\n\n\nBut this way we have to search each and every word from the begining in case of multiple data to search.The Knuth-Morris-Pratt string search algorithm<\/a> or KMP algorithm is an algorithm for finding a substring within another string that uses information calculated about the substring to speed up the search process.Before looking through the text to be searched, a table of jump lengths is calculated from the search string. Rather than iterating through the whole string, you can determine how many characters to skip over based on the structure of the word being searched for. As you scan through the search text and you find a mismatch, you can start comparing characters again from the last matching substring between the search term and the search text.E.g. if you are searching through \"Hello world how ya doin?\" for the words \u201cold world new\u201d, every time you find an instance of \u201dold world new\u201d that isn\u2019t followed by a line-break, you can skip the characters of checking the string and restart from the beginning of your words, because you know that they can\u2019t occur again within that span because you have already checked those and they don\u2019t match the begging of the search words. Basically you already know that index is the next occurence of world, so you can start again from there.<\/p>\n\n\n\n
\/\/ Construct a table with table[i] as the length of the longest prefix of the substring 0..i\n\/\/ create a table of size equal to the length of `str`\n\/\/ table[i] will store the prefix of the longest prefix of the substring str[0..i]\n\/\/ the longest prefix of the substring str[0] has length\n\/\/ for the substrings the following substrings, we have two cases\n\/\/ case 1. the current character doesn't match the last character of the longest prefix\n\/\/ if that is the case, we have to backtrack, and try find a character that will be equal to the current character\n\/\/ if we reach 0, then we couldn't find a chracter\n\/\/ case 2. The last character of the longest prefix matches the current character in `str`\n\/\/ if that is the case, we know that the longest prefix at position i has one more character.\n\/\/ for example consider `.` be any character not contained in the set [a.c]\n\/\/ str = abc....abc\n\/\/ consider `i` to be the last character `c` in `str`\n\/\/ maxPrefix = will be 2 (the first `c` in `str`)\n\/\/ maxPrefix now will be 3\n\/\/ so the max prefix for table[9] is 3\nfunction makeTable(str) {\n \n \n var table = new Array(str.length);\n var maxPrefix = 0;\n \n table[0] = 0;\n \n \n for (var i = 1; i < str.length; i++) {\n while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) {\n \n maxPrefix = table[maxPrefix - 1];\n }\n \n if (str.charAt(maxPrefix) === str.charAt(i)) {\n maxPrefix++;\n }\n table[i] = maxPrefix;\n }\n return table;\n }\n \n\/\/ Find all the words that matches in a given string `str`\n\/\/ this algorithm is based on the Knuth\u2013Morris\u2013Pratt algorithm. Its beauty consists in that it performs the matching in O(n)\n\/\/ find the prefix table in O(n)\n\/\/ `j` is the index in `word(P)`\n\/\/ `i` is the index in `str(S)`\n\/\/ Case 1. S[i] == P[j] so we move to the next index in `S` and `P`\n\/\/ Case 2. `j` is equal to the length of `P`\n\/\/ that means that we reached the end of `P` and thus we found a match\n\/\/ Next we have to update `j` because we want to save some time\n\/\/ instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far.\n\/\/ j-1 means the last character of `P` because j is actually `P.length`\n\/\/ e.g.\n\/\/ S = a b a b d e\n\/\/ P = `a b`a b\n\/\/ we will jump to `a b` and we will compare d and a in the next iteration\n\/\/ a b a b `d` e\n\/\/ a b `a` b\n\/\/ Case 3.\n\/\/ S[i] != P[j] There's a mismatch!\n\/\/ if we have found at least a character in common, do the same thing as in case 2\n\/\/ otherwise, j = 0, and we can move to the next character S[i+1]function kmpMatching(str, word) {\n \n var prefixes = makeTable(word);\n var matches = [];\n \n \n var j = 0;\n var i = 0;\n while (i < str.length) {\n \n if (str.charAt(i) === word.charAt(j)) {\n i++;\n j++;\n }\n \n if (j === word.length) {\n matches.push(i-j);\n \n j = prefixes[j-1];\n }\n \n else if (str.charAt(i) !== word.charAt(j)) {\n \n if (j !== 0) {\n j = prefixes[j-1];\n } else {\n \n i++;\n }\n }\n }\n \n return matches;\n }\n\nconsole.log(kmpMatching(\"it implies that it is very important\",\"impo\"))\n\noutput: [27]\n<\/pre>\n\n\n\nWe can implement these algorithms in real world applications.Hope it helps.There are many other algorithms to use. But for a start these might help.<\/p>\n\n\n\n
Happy coding.....<\/p>\n","post_title":"Searching Algorithms in JavaScript","post_excerpt":"The Searching Algorithm can be implemented with other languages as well. But here we will work with JavaScript to solve the Searching Algorithms. These algorithms are used to handle or work with the search related task in our projects or any applications that require searching. Searching is made easier by these algorithms. Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them.","post_status":"publish","comment_status":"open","ping_status":"open","post_password":"","post_name":"searching-algorithms-in-javascript","to_ping":"","pinged":"","post_modified":"2024-11-14 04:16:56","post_modified_gmt":"2024-11-14 04:16:56","post_content_filtered":"","post_parent":0,"guid":"https:\/\/blogue.tech\/?p=277","menu_order":0,"post_type":"post","post_mime_type":"","comment_count":"0","filter":"raw"}],"next":false,"prev":false,"total_page":1},"paged":1,"column_class":"jeg_col_3o3","class":"jnews_block_3"};
\nvar binarySearch = function(arr,elem){\n var start = 0;\n var end = arr.length - 1;\n var middle = Math.floor(start + end \/ 2);\n while(arr[middle] !== elem && start <= end){\n if(elem<arr[middle]){\n end=middle-1;\n }else{\n start = middle+1;\n }\n middle = Math.floor((start+end)\/2)\n }\n \/\/ if(arr[middle] === elem){\/\/ return middle;\/\/ }\/\/ return -1;\nreturn arr[middle] === elem ? middle : -1;\n}\n\n\nconsole.log(binarySearch([2,4,6,9,11,14,20,25,28,40],11)) \n\noutput: 4\n<\/pre>\n\n\n\n3.String Search<\/strong><\/h2>\n\n\n\n
This not totally related to linear search or Binary search. I just wanted to add it here as it is very much important for searching string. A very simple way to search strings is given below:<\/p>\n\n\n\n
Pseudocode:<\/u><\/strong><\/p>\n\n\n\n
\n
- Loop Over the longer string.<\/li>\n\n\n\n
- Loop Over the shorter string.<\/li>\n\n\n\n
- If the characters don't match,break out of the inner loop.<\/li>\n\n\n\n
- If the characters match,Keep going.<\/li>\n\n\n\n
- If you complete the inner loop and find a match, increment the count of matches.<\/li>\n\n\n\n
- Return the count<\/li>\n<\/ul>\n\n\n\n
function naiveSearch(str, word){\n var count = 0;\n for(var i = 0; i < str.length; i++){\n for(var j = 0; j < word.length; j++){\n if(word[j] !== str[i+j]) break;\n if(j === word.length - 1) count++;\n }\n }\n return count;\n}\n\n\nconsole.log(naiveSearch(\"search and find\", \"an\"))\n\noutput: [7]\n<\/pre>\n\n\n\nBut this way we have to search each and every word from the begining in case of multiple data to search.The Knuth-Morris-Pratt string search algorithm<\/a> or KMP algorithm is an algorithm for finding a substring within another string that uses information calculated about the substring to speed up the search process.Before looking through the text to be searched, a table of jump lengths is calculated from the search string. Rather than iterating through the whole string, you can determine how many characters to skip over based on the structure of the word being searched for. As you scan through the search text and you find a mismatch, you can start comparing characters again from the last matching substring between the search term and the search text.E.g. if you are searching through \"Hello world how ya doin?\" for the words \u201cold world new\u201d, every time you find an instance of \u201dold world new\u201d that isn\u2019t followed by a line-break, you can skip the characters of checking the string and restart from the beginning of your words, because you know that they can\u2019t occur again within that span because you have already checked those and they don\u2019t match the begging of the search words. Basically you already know that index is the next occurence of world, so you can start again from there.<\/p>\n\n\n\n
\/\/ Construct a table with table[i] as the length of the longest prefix of the substring 0..i\n\/\/ create a table of size equal to the length of `str`\n\/\/ table[i] will store the prefix of the longest prefix of the substring str[0..i]\n\/\/ the longest prefix of the substring str[0] has length\n\/\/ for the substrings the following substrings, we have two cases\n\/\/ case 1. the current character doesn't match the last character of the longest prefix\n\/\/ if that is the case, we have to backtrack, and try find a character that will be equal to the current character\n\/\/ if we reach 0, then we couldn't find a chracter\n\/\/ case 2. The last character of the longest prefix matches the current character in `str`\n\/\/ if that is the case, we know that the longest prefix at position i has one more character.\n\/\/ for example consider `.` be any character not contained in the set [a.c]\n\/\/ str = abc....abc\n\/\/ consider `i` to be the last character `c` in `str`\n\/\/ maxPrefix = will be 2 (the first `c` in `str`)\n\/\/ maxPrefix now will be 3\n\/\/ so the max prefix for table[9] is 3\nfunction makeTable(str) {\n \n \n var table = new Array(str.length);\n var maxPrefix = 0;\n \n table[0] = 0;\n \n \n for (var i = 1; i < str.length; i++) {\n while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) {\n \n maxPrefix = table[maxPrefix - 1];\n }\n \n if (str.charAt(maxPrefix) === str.charAt(i)) {\n maxPrefix++;\n }\n table[i] = maxPrefix;\n }\n return table;\n }\n \n\/\/ Find all the words that matches in a given string `str`\n\/\/ this algorithm is based on the Knuth\u2013Morris\u2013Pratt algorithm. Its beauty consists in that it performs the matching in O(n)\n\/\/ find the prefix table in O(n)\n\/\/ `j` is the index in `word(P)`\n\/\/ `i` is the index in `str(S)`\n\/\/ Case 1. S[i] == P[j] so we move to the next index in `S` and `P`\n\/\/ Case 2. `j` is equal to the length of `P`\n\/\/ that means that we reached the end of `P` and thus we found a match\n\/\/ Next we have to update `j` because we want to save some time\n\/\/ instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far.\n\/\/ j-1 means the last character of `P` because j is actually `P.length`\n\/\/ e.g.\n\/\/ S = a b a b d e\n\/\/ P = `a b`a b\n\/\/ we will jump to `a b` and we will compare d and a in the next iteration\n\/\/ a b a b `d` e\n\/\/ a b `a` b\n\/\/ Case 3.\n\/\/ S[i] != P[j] There's a mismatch!\n\/\/ if we have found at least a character in common, do the same thing as in case 2\n\/\/ otherwise, j = 0, and we can move to the next character S[i+1]function kmpMatching(str, word) {\n \n var prefixes = makeTable(word);\n var matches = [];\n \n \n var j = 0;\n var i = 0;\n while (i < str.length) {\n \n if (str.charAt(i) === word.charAt(j)) {\n i++;\n j++;\n }\n \n if (j === word.length) {\n matches.push(i-j);\n \n j = prefixes[j-1];\n }\n \n else if (str.charAt(i) !== word.charAt(j)) {\n \n if (j !== 0) {\n j = prefixes[j-1];\n } else {\n \n i++;\n }\n }\n }\n \n return matches;\n }\n\nconsole.log(kmpMatching(\"it implies that it is very important\",\"impo\"))\n\noutput: [27]\n<\/pre>\n\n\n\nWe can implement these algorithms in real world applications.Hope it helps.There are many other algorithms to use. But for a start these might help.<\/p>\n\n\n\n
Happy coding.....<\/p>\n","post_title":"Searching Algorithms in JavaScript","post_excerpt":"The Searching Algorithm can be implemented with other languages as well. But here we will work with JavaScript to solve the Searching Algorithms. These algorithms are used to handle or work with the search related task in our projects or any applications that require searching. Searching is made easier by these algorithms. Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them.","post_status":"publish","comment_status":"open","ping_status":"open","post_password":"","post_name":"searching-algorithms-in-javascript","to_ping":"","pinged":"","post_modified":"2024-11-14 04:16:56","post_modified_gmt":"2024-11-14 04:16:56","post_content_filtered":"","post_parent":0,"guid":"https:\/\/blogue.tech\/?p=277","menu_order":0,"post_type":"post","post_mime_type":"","comment_count":"0","filter":"raw"}],"next":false,"prev":false,"total_page":1},"paged":1,"column_class":"jeg_col_3o3","class":"jnews_block_3"};
\n- If you never find the value,return -1.<\/li>\n<\/ul>\n\n\n\n
var binarySearch = function(arr,elem){\n var start = 0;\n var end = arr.length - 1;\n var middle = Math.floor(start + end \/ 2);\n while(arr[middle] !== elem && start <= end){\n if(elem<arr[middle]){\n end=middle-1;\n }else{\n start = middle+1;\n }\n middle = Math.floor((start+end)\/2)\n }\n \/\/ if(arr[middle] === elem){\/\/ return middle;\/\/ }\/\/ return -1;\nreturn arr[middle] === elem ? middle : -1;\n}\n\n\nconsole.log(binarySearch([2,4,6,9,11,14,20,25,28,40],11)) \n\noutput: 4\n<\/pre>\n\n\n\n3.String Search<\/strong><\/h2>\n\n\n\n
This not totally related to linear search or Binary search. I just wanted to add it here as it is very much important for searching string. A very simple way to search strings is given below:<\/p>\n\n\n\n
Pseudocode:<\/u><\/strong><\/p>\n\n\n\n
\n
- Loop Over the longer string.<\/li>\n\n\n\n
- Loop Over the shorter string.<\/li>\n\n\n\n
- If the characters don't match,break out of the inner loop.<\/li>\n\n\n\n
- If the characters match,Keep going.<\/li>\n\n\n\n
- If you complete the inner loop and find a match, increment the count of matches.<\/li>\n\n\n\n
- Return the count<\/li>\n<\/ul>\n\n\n\n
function naiveSearch(str, word){\n var count = 0;\n for(var i = 0; i < str.length; i++){\n for(var j = 0; j < word.length; j++){\n if(word[j] !== str[i+j]) break;\n if(j === word.length - 1) count++;\n }\n }\n return count;\n}\n\n\nconsole.log(naiveSearch(\"search and find\", \"an\"))\n\noutput: [7]\n<\/pre>\n\n\n\nBut this way we have to search each and every word from the begining in case of multiple data to search.The Knuth-Morris-Pratt string search algorithm<\/a> or KMP algorithm is an algorithm for finding a substring within another string that uses information calculated about the substring to speed up the search process.Before looking through the text to be searched, a table of jump lengths is calculated from the search string. Rather than iterating through the whole string, you can determine how many characters to skip over based on the structure of the word being searched for. As you scan through the search text and you find a mismatch, you can start comparing characters again from the last matching substring between the search term and the search text.E.g. if you are searching through \"Hello world how ya doin?\" for the words \u201cold world new\u201d, every time you find an instance of \u201dold world new\u201d that isn\u2019t followed by a line-break, you can skip the characters of checking the string and restart from the beginning of your words, because you know that they can\u2019t occur again within that span because you have already checked those and they don\u2019t match the begging of the search words. Basically you already know that index is the next occurence of world, so you can start again from there.<\/p>\n\n\n\n
\/\/ Construct a table with table[i] as the length of the longest prefix of the substring 0..i\n\/\/ create a table of size equal to the length of `str`\n\/\/ table[i] will store the prefix of the longest prefix of the substring str[0..i]\n\/\/ the longest prefix of the substring str[0] has length\n\/\/ for the substrings the following substrings, we have two cases\n\/\/ case 1. the current character doesn't match the last character of the longest prefix\n\/\/ if that is the case, we have to backtrack, and try find a character that will be equal to the current character\n\/\/ if we reach 0, then we couldn't find a chracter\n\/\/ case 2. The last character of the longest prefix matches the current character in `str`\n\/\/ if that is the case, we know that the longest prefix at position i has one more character.\n\/\/ for example consider `.` be any character not contained in the set [a.c]\n\/\/ str = abc....abc\n\/\/ consider `i` to be the last character `c` in `str`\n\/\/ maxPrefix = will be 2 (the first `c` in `str`)\n\/\/ maxPrefix now will be 3\n\/\/ so the max prefix for table[9] is 3\nfunction makeTable(str) {\n \n \n var table = new Array(str.length);\n var maxPrefix = 0;\n \n table[0] = 0;\n \n \n for (var i = 1; i < str.length; i++) {\n while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) {\n \n maxPrefix = table[maxPrefix - 1];\n }\n \n if (str.charAt(maxPrefix) === str.charAt(i)) {\n maxPrefix++;\n }\n table[i] = maxPrefix;\n }\n return table;\n }\n \n\/\/ Find all the words that matches in a given string `str`\n\/\/ this algorithm is based on the Knuth\u2013Morris\u2013Pratt algorithm. Its beauty consists in that it performs the matching in O(n)\n\/\/ find the prefix table in O(n)\n\/\/ `j` is the index in `word(P)`\n\/\/ `i` is the index in `str(S)`\n\/\/ Case 1. S[i] == P[j] so we move to the next index in `S` and `P`\n\/\/ Case 2. `j` is equal to the length of `P`\n\/\/ that means that we reached the end of `P` and thus we found a match\n\/\/ Next we have to update `j` because we want to save some time\n\/\/ instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far.\n\/\/ j-1 means the last character of `P` because j is actually `P.length`\n\/\/ e.g.\n\/\/ S = a b a b d e\n\/\/ P = `a b`a b\n\/\/ we will jump to `a b` and we will compare d and a in the next iteration\n\/\/ a b a b `d` e\n\/\/ a b `a` b\n\/\/ Case 3.\n\/\/ S[i] != P[j] There's a mismatch!\n\/\/ if we have found at least a character in common, do the same thing as in case 2\n\/\/ otherwise, j = 0, and we can move to the next character S[i+1]function kmpMatching(str, word) {\n \n var prefixes = makeTable(word);\n var matches = [];\n \n \n var j = 0;\n var i = 0;\n while (i < str.length) {\n \n if (str.charAt(i) === word.charAt(j)) {\n i++;\n j++;\n }\n \n if (j === word.length) {\n matches.push(i-j);\n \n j = prefixes[j-1];\n }\n \n else if (str.charAt(i) !== word.charAt(j)) {\n \n if (j !== 0) {\n j = prefixes[j-1];\n } else {\n \n i++;\n }\n }\n }\n \n return matches;\n }\n\nconsole.log(kmpMatching(\"it implies that it is very important\",\"impo\"))\n\noutput: [27]\n<\/pre>\n\n\n\nWe can implement these algorithms in real world applications.Hope it helps.There are many other algorithms to use. But for a start these might help.<\/p>\n\n\n\n
Happy coding.....<\/p>\n","post_title":"Searching Algorithms in JavaScript","post_excerpt":"The Searching Algorithm can be implemented with other languages as well. But here we will work with JavaScript to solve the Searching Algorithms. These algorithms are used to handle or work with the search related task in our projects or any applications that require searching. Searching is made easier by these algorithms. Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them.","post_status":"publish","comment_status":"open","ping_status":"open","post_password":"","post_name":"searching-algorithms-in-javascript","to_ping":"","pinged":"","post_modified":"2024-11-14 04:16:56","post_modified_gmt":"2024-11-14 04:16:56","post_content_filtered":"","post_parent":0,"guid":"https:\/\/blogue.tech\/?p=277","menu_order":0,"post_type":"post","post_mime_type":"","comment_count":"0","filter":"raw"}],"next":false,"prev":false,"total_page":1},"paged":1,"column_class":"jeg_col_3o3","class":"jnews_block_3"};
\n- If the value is too large,move the right pointer down.<\/li>\n\n\n\n
- If you never find the value,return -1.<\/li>\n<\/ul>\n\n\n\n
var binarySearch = function(arr,elem){\n var start = 0;\n var end = arr.length - 1;\n var middle = Math.floor(start + end \/ 2);\n while(arr[middle] !== elem && start <= end){\n if(elem<arr[middle]){\n end=middle-1;\n }else{\n start = middle+1;\n }\n middle = Math.floor((start+end)\/2)\n }\n \/\/ if(arr[middle] === elem){\/\/ return middle;\/\/ }\/\/ return -1;\nreturn arr[middle] === elem ? middle : -1;\n}\n\n\nconsole.log(binarySearch([2,4,6,9,11,14,20,25,28,40],11)) \n\noutput: 4\n<\/pre>\n\n\n\n3.String Search<\/strong><\/h2>\n\n\n\n
This not totally related to linear search or Binary search. I just wanted to add it here as it is very much important for searching string. A very simple way to search strings is given below:<\/p>\n\n\n\n
Pseudocode:<\/u><\/strong><\/p>\n\n\n\n
\n
- Loop Over the longer string.<\/li>\n\n\n\n
- Loop Over the shorter string.<\/li>\n\n\n\n
- If the characters don't match,break out of the inner loop.<\/li>\n\n\n\n
- If the characters match,Keep going.<\/li>\n\n\n\n
- If you complete the inner loop and find a match, increment the count of matches.<\/li>\n\n\n\n
- Return the count<\/li>\n<\/ul>\n\n\n\n
function naiveSearch(str, word){\n var count = 0;\n for(var i = 0; i < str.length; i++){\n for(var j = 0; j < word.length; j++){\n if(word[j] !== str[i+j]) break;\n if(j === word.length - 1) count++;\n }\n }\n return count;\n}\n\n\nconsole.log(naiveSearch(\"search and find\", \"an\"))\n\noutput: [7]\n<\/pre>\n\n\n\nBut this way we have to search each and every word from the begining in case of multiple data to search.The Knuth-Morris-Pratt string search algorithm<\/a> or KMP algorithm is an algorithm for finding a substring within another string that uses information calculated about the substring to speed up the search process.Before looking through the text to be searched, a table of jump lengths is calculated from the search string. Rather than iterating through the whole string, you can determine how many characters to skip over based on the structure of the word being searched for. As you scan through the search text and you find a mismatch, you can start comparing characters again from the last matching substring between the search term and the search text.E.g. if you are searching through \"Hello world how ya doin?\" for the words \u201cold world new\u201d, every time you find an instance of \u201dold world new\u201d that isn\u2019t followed by a line-break, you can skip the characters of checking the string and restart from the beginning of your words, because you know that they can\u2019t occur again within that span because you have already checked those and they don\u2019t match the begging of the search words. Basically you already know that index is the next occurence of world, so you can start again from there.<\/p>\n\n\n\n
\/\/ Construct a table with table[i] as the length of the longest prefix of the substring 0..i\n\/\/ create a table of size equal to the length of `str`\n\/\/ table[i] will store the prefix of the longest prefix of the substring str[0..i]\n\/\/ the longest prefix of the substring str[0] has length\n\/\/ for the substrings the following substrings, we have two cases\n\/\/ case 1. the current character doesn't match the last character of the longest prefix\n\/\/ if that is the case, we have to backtrack, and try find a character that will be equal to the current character\n\/\/ if we reach 0, then we couldn't find a chracter\n\/\/ case 2. The last character of the longest prefix matches the current character in `str`\n\/\/ if that is the case, we know that the longest prefix at position i has one more character.\n\/\/ for example consider `.` be any character not contained in the set [a.c]\n\/\/ str = abc....abc\n\/\/ consider `i` to be the last character `c` in `str`\n\/\/ maxPrefix = will be 2 (the first `c` in `str`)\n\/\/ maxPrefix now will be 3\n\/\/ so the max prefix for table[9] is 3\nfunction makeTable(str) {\n \n \n var table = new Array(str.length);\n var maxPrefix = 0;\n \n table[0] = 0;\n \n \n for (var i = 1; i < str.length; i++) {\n while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) {\n \n maxPrefix = table[maxPrefix - 1];\n }\n \n if (str.charAt(maxPrefix) === str.charAt(i)) {\n maxPrefix++;\n }\n table[i] = maxPrefix;\n }\n return table;\n }\n \n\/\/ Find all the words that matches in a given string `str`\n\/\/ this algorithm is based on the Knuth\u2013Morris\u2013Pratt algorithm. Its beauty consists in that it performs the matching in O(n)\n\/\/ find the prefix table in O(n)\n\/\/ `j` is the index in `word(P)`\n\/\/ `i` is the index in `str(S)`\n\/\/ Case 1. S[i] == P[j] so we move to the next index in `S` and `P`\n\/\/ Case 2. `j` is equal to the length of `P`\n\/\/ that means that we reached the end of `P` and thus we found a match\n\/\/ Next we have to update `j` because we want to save some time\n\/\/ instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far.\n\/\/ j-1 means the last character of `P` because j is actually `P.length`\n\/\/ e.g.\n\/\/ S = a b a b d e\n\/\/ P = `a b`a b\n\/\/ we will jump to `a b` and we will compare d and a in the next iteration\n\/\/ a b a b `d` e\n\/\/ a b `a` b\n\/\/ Case 3.\n\/\/ S[i] != P[j] There's a mismatch!\n\/\/ if we have found at least a character in common, do the same thing as in case 2\n\/\/ otherwise, j = 0, and we can move to the next character S[i+1]function kmpMatching(str, word) {\n \n var prefixes = makeTable(word);\n var matches = [];\n \n \n var j = 0;\n var i = 0;\n while (i < str.length) {\n \n if (str.charAt(i) === word.charAt(j)) {\n i++;\n j++;\n }\n \n if (j === word.length) {\n matches.push(i-j);\n \n j = prefixes[j-1];\n }\n \n else if (str.charAt(i) !== word.charAt(j)) {\n \n if (j !== 0) {\n j = prefixes[j-1];\n } else {\n \n i++;\n }\n }\n }\n \n return matches;\n }\n\nconsole.log(kmpMatching(\"it implies that it is very important\",\"impo\"))\n\noutput: [27]\n<\/pre>\n\n\n\nWe can implement these algorithms in real world applications.Hope it helps.There are many other algorithms to use. But for a start these might help.<\/p>\n\n\n\n
Happy coding.....<\/p>\n","post_title":"Searching Algorithms in JavaScript","post_excerpt":"The Searching Algorithm can be implemented with other languages as well. But here we will work with JavaScript to solve the Searching Algorithms. These algorithms are used to handle or work with the search related task in our projects or any applications that require searching. Searching is made easier by these algorithms. Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them.","post_status":"publish","comment_status":"open","ping_status":"open","post_password":"","post_name":"searching-algorithms-in-javascript","to_ping":"","pinged":"","post_modified":"2024-11-14 04:16:56","post_modified_gmt":"2024-11-14 04:16:56","post_content_filtered":"","post_parent":0,"guid":"https:\/\/blogue.tech\/?p=277","menu_order":0,"post_type":"post","post_mime_type":"","comment_count":"0","filter":"raw"}],"next":false,"prev":false,"total_page":1},"paged":1,"column_class":"jeg_col_3o3","class":"jnews_block_3"};
\n- If the value is too small,move the left pointer up.<\/li>\n\n\n\n
- If the value is too large,move the right pointer down.<\/li>\n\n\n\n
- If you never find the value,return -1.<\/li>\n<\/ul>\n\n\n\n
var binarySearch = function(arr,elem){\n var start = 0;\n var end = arr.length - 1;\n var middle = Math.floor(start + end \/ 2);\n while(arr[middle] !== elem && start <= end){\n if(elem<arr[middle]){\n end=middle-1;\n }else{\n start = middle+1;\n }\n middle = Math.floor((start+end)\/2)\n }\n \/\/ if(arr[middle] === elem){\/\/ return middle;\/\/ }\/\/ return -1;\nreturn arr[middle] === elem ? middle : -1;\n}\n\n\nconsole.log(binarySearch([2,4,6,9,11,14,20,25,28,40],11)) \n\noutput: 4\n<\/pre>\n\n\n\n3.String Search<\/strong><\/h2>\n\n\n\n
This not totally related to linear search or Binary search. I just wanted to add it here as it is very much important for searching string. A very simple way to search strings is given below:<\/p>\n\n\n\n
Pseudocode:<\/u><\/strong><\/p>\n\n\n\n
\n
- Loop Over the longer string.<\/li>\n\n\n\n
- Loop Over the shorter string.<\/li>\n\n\n\n
- If the characters don't match,break out of the inner loop.<\/li>\n\n\n\n
- If the characters match,Keep going.<\/li>\n\n\n\n
- If you complete the inner loop and find a match, increment the count of matches.<\/li>\n\n\n\n
- Return the count<\/li>\n<\/ul>\n\n\n\n
function naiveSearch(str, word){\n var count = 0;\n for(var i = 0; i < str.length; i++){\n for(var j = 0; j < word.length; j++){\n if(word[j] !== str[i+j]) break;\n if(j === word.length - 1) count++;\n }\n }\n return count;\n}\n\n\nconsole.log(naiveSearch(\"search and find\", \"an\"))\n\noutput: [7]\n<\/pre>\n\n\n\nBut this way we have to search each and every word from the begining in case of multiple data to search.The Knuth-Morris-Pratt string search algorithm<\/a> or KMP algorithm is an algorithm for finding a substring within another string that uses information calculated about the substring to speed up the search process.Before looking through the text to be searched, a table of jump lengths is calculated from the search string. Rather than iterating through the whole string, you can determine how many characters to skip over based on the structure of the word being searched for. As you scan through the search text and you find a mismatch, you can start comparing characters again from the last matching substring between the search term and the search text.E.g. if you are searching through \"Hello world how ya doin?\" for the words \u201cold world new\u201d, every time you find an instance of \u201dold world new\u201d that isn\u2019t followed by a line-break, you can skip the characters of checking the string and restart from the beginning of your words, because you know that they can\u2019t occur again within that span because you have already checked those and they don\u2019t match the begging of the search words. Basically you already know that index is the next occurence of world, so you can start again from there.<\/p>\n\n\n\n
\/\/ Construct a table with table[i] as the length of the longest prefix of the substring 0..i\n\/\/ create a table of size equal to the length of `str`\n\/\/ table[i] will store the prefix of the longest prefix of the substring str[0..i]\n\/\/ the longest prefix of the substring str[0] has length\n\/\/ for the substrings the following substrings, we have two cases\n\/\/ case 1. the current character doesn't match the last character of the longest prefix\n\/\/ if that is the case, we have to backtrack, and try find a character that will be equal to the current character\n\/\/ if we reach 0, then we couldn't find a chracter\n\/\/ case 2. The last character of the longest prefix matches the current character in `str`\n\/\/ if that is the case, we know that the longest prefix at position i has one more character.\n\/\/ for example consider `.` be any character not contained in the set [a.c]\n\/\/ str = abc....abc\n\/\/ consider `i` to be the last character `c` in `str`\n\/\/ maxPrefix = will be 2 (the first `c` in `str`)\n\/\/ maxPrefix now will be 3\n\/\/ so the max prefix for table[9] is 3\nfunction makeTable(str) {\n \n \n var table = new Array(str.length);\n var maxPrefix = 0;\n \n table[0] = 0;\n \n \n for (var i = 1; i < str.length; i++) {\n while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) {\n \n maxPrefix = table[maxPrefix - 1];\n }\n \n if (str.charAt(maxPrefix) === str.charAt(i)) {\n maxPrefix++;\n }\n table[i] = maxPrefix;\n }\n return table;\n }\n \n\/\/ Find all the words that matches in a given string `str`\n\/\/ this algorithm is based on the Knuth\u2013Morris\u2013Pratt algorithm. Its beauty consists in that it performs the matching in O(n)\n\/\/ find the prefix table in O(n)\n\/\/ `j` is the index in `word(P)`\n\/\/ `i` is the index in `str(S)`\n\/\/ Case 1. S[i] == P[j] so we move to the next index in `S` and `P`\n\/\/ Case 2. `j` is equal to the length of `P`\n\/\/ that means that we reached the end of `P` and thus we found a match\n\/\/ Next we have to update `j` because we want to save some time\n\/\/ instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far.\n\/\/ j-1 means the last character of `P` because j is actually `P.length`\n\/\/ e.g.\n\/\/ S = a b a b d e\n\/\/ P = `a b`a b\n\/\/ we will jump to `a b` and we will compare d and a in the next iteration\n\/\/ a b a b `d` e\n\/\/ a b `a` b\n\/\/ Case 3.\n\/\/ S[i] != P[j] There's a mismatch!\n\/\/ if we have found at least a character in common, do the same thing as in case 2\n\/\/ otherwise, j = 0, and we can move to the next character S[i+1]function kmpMatching(str, word) {\n \n var prefixes = makeTable(word);\n var matches = [];\n \n \n var j = 0;\n var i = 0;\n while (i < str.length) {\n \n if (str.charAt(i) === word.charAt(j)) {\n i++;\n j++;\n }\n \n if (j === word.length) {\n matches.push(i-j);\n \n j = prefixes[j-1];\n }\n \n else if (str.charAt(i) !== word.charAt(j)) {\n \n if (j !== 0) {\n j = prefixes[j-1];\n } else {\n \n i++;\n }\n }\n }\n \n return matches;\n }\n\nconsole.log(kmpMatching(\"it implies that it is very important\",\"impo\"))\n\noutput: [27]\n<\/pre>\n\n\n\nWe can implement these algorithms in real world applications.Hope it helps.There are many other algorithms to use. But for a start these might help.<\/p>\n\n\n\n
Happy coding.....<\/p>\n","post_title":"Searching Algorithms in JavaScript","post_excerpt":"The Searching Algorithm can be implemented with other languages as well. But here we will work with JavaScript to solve the Searching Algorithms. These algorithms are used to handle or work with the search related task in our projects or any applications that require searching. Searching is made easier by these algorithms. Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them.","post_status":"publish","comment_status":"open","ping_status":"open","post_password":"","post_name":"searching-algorithms-in-javascript","to_ping":"","pinged":"","post_modified":"2024-11-14 04:16:56","post_modified_gmt":"2024-11-14 04:16:56","post_content_filtered":"","post_parent":0,"guid":"https:\/\/blogue.tech\/?p=277","menu_order":0,"post_type":"post","post_mime_type":"","comment_count":"0","filter":"raw"}],"next":false,"prev":false,"total_page":1},"paged":1,"column_class":"jeg_col_3o3","class":"jnews_block_3"};
\n- If you find the value you want,return the index.<\/li>\n\n\n\n
- If the value is too small,move the left pointer up.<\/li>\n\n\n\n
- If the value is too large,move the right pointer down.<\/li>\n\n\n\n
- If you never find the value,return -1.<\/li>\n<\/ul>\n\n\n\n
var binarySearch = function(arr,elem){\n var start = 0;\n var end = arr.length - 1;\n var middle = Math.floor(start + end \/ 2);\n while(arr[middle] !== elem && start <= end){\n if(elem<arr[middle]){\n end=middle-1;\n }else{\n start = middle+1;\n }\n middle = Math.floor((start+end)\/2)\n }\n \/\/ if(arr[middle] === elem){\/\/ return middle;\/\/ }\/\/ return -1;\nreturn arr[middle] === elem ? middle : -1;\n}\n\n\nconsole.log(binarySearch([2,4,6,9,11,14,20,25,28,40],11)) \n\noutput: 4\n<\/pre>\n\n\n\n3.String Search<\/strong><\/h2>\n\n\n\n
This not totally related to linear search or Binary search. I just wanted to add it here as it is very much important for searching string. A very simple way to search strings is given below:<\/p>\n\n\n\n
Pseudocode:<\/u><\/strong><\/p>\n\n\n\n
\n
- Loop Over the longer string.<\/li>\n\n\n\n
- Loop Over the shorter string.<\/li>\n\n\n\n
- If the characters don't match,break out of the inner loop.<\/li>\n\n\n\n
- If the characters match,Keep going.<\/li>\n\n\n\n
- If you complete the inner loop and find a match, increment the count of matches.<\/li>\n\n\n\n
- Return the count<\/li>\n<\/ul>\n\n\n\n
function naiveSearch(str, word){\n var count = 0;\n for(var i = 0; i < str.length; i++){\n for(var j = 0; j < word.length; j++){\n if(word[j] !== str[i+j]) break;\n if(j === word.length - 1) count++;\n }\n }\n return count;\n}\n\n\nconsole.log(naiveSearch(\"search and find\", \"an\"))\n\noutput: [7]\n<\/pre>\n\n\n\nBut this way we have to search each and every word from the begining in case of multiple data to search.The Knuth-Morris-Pratt string search algorithm<\/a> or KMP algorithm is an algorithm for finding a substring within another string that uses information calculated about the substring to speed up the search process.Before looking through the text to be searched, a table of jump lengths is calculated from the search string. Rather than iterating through the whole string, you can determine how many characters to skip over based on the structure of the word being searched for. As you scan through the search text and you find a mismatch, you can start comparing characters again from the last matching substring between the search term and the search text.E.g. if you are searching through \"Hello world how ya doin?\" for the words \u201cold world new\u201d, every time you find an instance of \u201dold world new\u201d that isn\u2019t followed by a line-break, you can skip the characters of checking the string and restart from the beginning of your words, because you know that they can\u2019t occur again within that span because you have already checked those and they don\u2019t match the begging of the search words. Basically you already know that index is the next occurence of world, so you can start again from there.<\/p>\n\n\n\n
\/\/ Construct a table with table[i] as the length of the longest prefix of the substring 0..i\n\/\/ create a table of size equal to the length of `str`\n\/\/ table[i] will store the prefix of the longest prefix of the substring str[0..i]\n\/\/ the longest prefix of the substring str[0] has length\n\/\/ for the substrings the following substrings, we have two cases\n\/\/ case 1. the current character doesn't match the last character of the longest prefix\n\/\/ if that is the case, we have to backtrack, and try find a character that will be equal to the current character\n\/\/ if we reach 0, then we couldn't find a chracter\n\/\/ case 2. The last character of the longest prefix matches the current character in `str`\n\/\/ if that is the case, we know that the longest prefix at position i has one more character.\n\/\/ for example consider `.` be any character not contained in the set [a.c]\n\/\/ str = abc....abc\n\/\/ consider `i` to be the last character `c` in `str`\n\/\/ maxPrefix = will be 2 (the first `c` in `str`)\n\/\/ maxPrefix now will be 3\n\/\/ so the max prefix for table[9] is 3\nfunction makeTable(str) {\n \n \n var table = new Array(str.length);\n var maxPrefix = 0;\n \n table[0] = 0;\n \n \n for (var i = 1; i < str.length; i++) {\n while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) {\n \n maxPrefix = table[maxPrefix - 1];\n }\n \n if (str.charAt(maxPrefix) === str.charAt(i)) {\n maxPrefix++;\n }\n table[i] = maxPrefix;\n }\n return table;\n }\n \n\/\/ Find all the words that matches in a given string `str`\n\/\/ this algorithm is based on the Knuth\u2013Morris\u2013Pratt algorithm. Its beauty consists in that it performs the matching in O(n)\n\/\/ find the prefix table in O(n)\n\/\/ `j` is the index in `word(P)`\n\/\/ `i` is the index in `str(S)`\n\/\/ Case 1. S[i] == P[j] so we move to the next index in `S` and `P`\n\/\/ Case 2. `j` is equal to the length of `P`\n\/\/ that means that we reached the end of `P` and thus we found a match\n\/\/ Next we have to update `j` because we want to save some time\n\/\/ instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far.\n\/\/ j-1 means the last character of `P` because j is actually `P.length`\n\/\/ e.g.\n\/\/ S = a b a b d e\n\/\/ P = `a b`a b\n\/\/ we will jump to `a b` and we will compare d and a in the next iteration\n\/\/ a b a b `d` e\n\/\/ a b `a` b\n\/\/ Case 3.\n\/\/ S[i] != P[j] There's a mismatch!\n\/\/ if we have found at least a character in common, do the same thing as in case 2\n\/\/ otherwise, j = 0, and we can move to the next character S[i+1]function kmpMatching(str, word) {\n \n var prefixes = makeTable(word);\n var matches = [];\n \n \n var j = 0;\n var i = 0;\n while (i < str.length) {\n \n if (str.charAt(i) === word.charAt(j)) {\n i++;\n j++;\n }\n \n if (j === word.length) {\n matches.push(i-j);\n \n j = prefixes[j-1];\n }\n \n else if (str.charAt(i) !== word.charAt(j)) {\n \n if (j !== 0) {\n j = prefixes[j-1];\n } else {\n \n i++;\n }\n }\n }\n \n return matches;\n }\n\nconsole.log(kmpMatching(\"it implies that it is very important\",\"impo\"))\n\noutput: [27]\n<\/pre>\n\n\n\nWe can implement these algorithms in real world applications.Hope it helps.There are many other algorithms to use. But for a start these might help.<\/p>\n\n\n\n
Happy coding.....<\/p>\n","post_title":"Searching Algorithms in JavaScript","post_excerpt":"The Searching Algorithm can be implemented with other languages as well. But here we will work with JavaScript to solve the Searching Algorithms. These algorithms are used to handle or work with the search related task in our projects or any applications that require searching. Searching is made easier by these algorithms. Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them.","post_status":"publish","comment_status":"open","ping_status":"open","post_password":"","post_name":"searching-algorithms-in-javascript","to_ping":"","pinged":"","post_modified":"2024-11-14 04:16:56","post_modified_gmt":"2024-11-14 04:16:56","post_content_filtered":"","post_parent":0,"guid":"https:\/\/blogue.tech\/?p=277","menu_order":0,"post_type":"post","post_mime_type":"","comment_count":"0","filter":"raw"}],"next":false,"prev":false,"total_page":1},"paged":1,"column_class":"jeg_col_3o3","class":"jnews_block_3"};
\n- Create a pointer in the middle.<\/li>\n\n\n\n
- If you find the value you want,return the index.<\/li>\n\n\n\n
- If the value is too small,move the left pointer up.<\/li>\n\n\n\n
- If the value is too large,move the right pointer down.<\/li>\n\n\n\n
- If you never find the value,return -1.<\/li>\n<\/ul>\n\n\n\n
var binarySearch = function(arr,elem){\n var start = 0;\n var end = arr.length - 1;\n var middle = Math.floor(start + end \/ 2);\n while(arr[middle] !== elem && start <= end){\n if(elem<arr[middle]){\n end=middle-1;\n }else{\n start = middle+1;\n }\n middle = Math.floor((start+end)\/2)\n }\n \/\/ if(arr[middle] === elem){\/\/ return middle;\/\/ }\/\/ return -1;\nreturn arr[middle] === elem ? middle : -1;\n}\n\n\nconsole.log(binarySearch([2,4,6,9,11,14,20,25,28,40],11)) \n\noutput: 4\n<\/pre>\n\n\n\n3.String Search<\/strong><\/h2>\n\n\n\n
This not totally related to linear search or Binary search. I just wanted to add it here as it is very much important for searching string. A very simple way to search strings is given below:<\/p>\n\n\n\n
Pseudocode:<\/u><\/strong><\/p>\n\n\n\n
\n
- Loop Over the longer string.<\/li>\n\n\n\n
- Loop Over the shorter string.<\/li>\n\n\n\n
- If the characters don't match,break out of the inner loop.<\/li>\n\n\n\n
- If the characters match,Keep going.<\/li>\n\n\n\n
- If you complete the inner loop and find a match, increment the count of matches.<\/li>\n\n\n\n
- Return the count<\/li>\n<\/ul>\n\n\n\n
function naiveSearch(str, word){\n var count = 0;\n for(var i = 0; i < str.length; i++){\n for(var j = 0; j < word.length; j++){\n if(word[j] !== str[i+j]) break;\n if(j === word.length - 1) count++;\n }\n }\n return count;\n}\n\n\nconsole.log(naiveSearch(\"search and find\", \"an\"))\n\noutput: [7]\n<\/pre>\n\n\n\nBut this way we have to search each and every word from the begining in case of multiple data to search.The Knuth-Morris-Pratt string search algorithm<\/a> or KMP algorithm is an algorithm for finding a substring within another string that uses information calculated about the substring to speed up the search process.Before looking through the text to be searched, a table of jump lengths is calculated from the search string. Rather than iterating through the whole string, you can determine how many characters to skip over based on the structure of the word being searched for. As you scan through the search text and you find a mismatch, you can start comparing characters again from the last matching substring between the search term and the search text.E.g. if you are searching through \"Hello world how ya doin?\" for the words \u201cold world new\u201d, every time you find an instance of \u201dold world new\u201d that isn\u2019t followed by a line-break, you can skip the characters of checking the string and restart from the beginning of your words, because you know that they can\u2019t occur again within that span because you have already checked those and they don\u2019t match the begging of the search words. Basically you already know that index is the next occurence of world, so you can start again from there.<\/p>\n\n\n\n
\/\/ Construct a table with table[i] as the length of the longest prefix of the substring 0..i\n\/\/ create a table of size equal to the length of `str`\n\/\/ table[i] will store the prefix of the longest prefix of the substring str[0..i]\n\/\/ the longest prefix of the substring str[0] has length\n\/\/ for the substrings the following substrings, we have two cases\n\/\/ case 1. the current character doesn't match the last character of the longest prefix\n\/\/ if that is the case, we have to backtrack, and try find a character that will be equal to the current character\n\/\/ if we reach 0, then we couldn't find a chracter\n\/\/ case 2. The last character of the longest prefix matches the current character in `str`\n\/\/ if that is the case, we know that the longest prefix at position i has one more character.\n\/\/ for example consider `.` be any character not contained in the set [a.c]\n\/\/ str = abc....abc\n\/\/ consider `i` to be the last character `c` in `str`\n\/\/ maxPrefix = will be 2 (the first `c` in `str`)\n\/\/ maxPrefix now will be 3\n\/\/ so the max prefix for table[9] is 3\nfunction makeTable(str) {\n \n \n var table = new Array(str.length);\n var maxPrefix = 0;\n \n table[0] = 0;\n \n \n for (var i = 1; i < str.length; i++) {\n while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) {\n \n maxPrefix = table[maxPrefix - 1];\n }\n \n if (str.charAt(maxPrefix) === str.charAt(i)) {\n maxPrefix++;\n }\n table[i] = maxPrefix;\n }\n return table;\n }\n \n\/\/ Find all the words that matches in a given string `str`\n\/\/ this algorithm is based on the Knuth\u2013Morris\u2013Pratt algorithm. Its beauty consists in that it performs the matching in O(n)\n\/\/ find the prefix table in O(n)\n\/\/ `j` is the index in `word(P)`\n\/\/ `i` is the index in `str(S)`\n\/\/ Case 1. S[i] == P[j] so we move to the next index in `S` and `P`\n\/\/ Case 2. `j` is equal to the length of `P`\n\/\/ that means that we reached the end of `P` and thus we found a match\n\/\/ Next we have to update `j` because we want to save some time\n\/\/ instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far.\n\/\/ j-1 means the last character of `P` because j is actually `P.length`\n\/\/ e.g.\n\/\/ S = a b a b d e\n\/\/ P = `a b`a b\n\/\/ we will jump to `a b` and we will compare d and a in the next iteration\n\/\/ a b a b `d` e\n\/\/ a b `a` b\n\/\/ Case 3.\n\/\/ S[i] != P[j] There's a mismatch!\n\/\/ if we have found at least a character in common, do the same thing as in case 2\n\/\/ otherwise, j = 0, and we can move to the next character S[i+1]function kmpMatching(str, word) {\n \n var prefixes = makeTable(word);\n var matches = [];\n \n \n var j = 0;\n var i = 0;\n while (i < str.length) {\n \n if (str.charAt(i) === word.charAt(j)) {\n i++;\n j++;\n }\n \n if (j === word.length) {\n matches.push(i-j);\n \n j = prefixes[j-1];\n }\n \n else if (str.charAt(i) !== word.charAt(j)) {\n \n if (j !== 0) {\n j = prefixes[j-1];\n } else {\n \n i++;\n }\n }\n }\n \n return matches;\n }\n\nconsole.log(kmpMatching(\"it implies that it is very important\",\"impo\"))\n\noutput: [27]\n<\/pre>\n\n\n\nWe can implement these algorithms in real world applications.Hope it helps.There are many other algorithms to use. But for a start these might help.<\/p>\n\n\n\n
Happy coding.....<\/p>\n","post_title":"Searching Algorithms in JavaScript","post_excerpt":"The Searching Algorithm can be implemented with other languages as well. But here we will work with JavaScript to solve the Searching Algorithms. These algorithms are used to handle or work with the search related task in our projects or any applications that require searching. Searching is made easier by these algorithms. Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them.","post_status":"publish","comment_status":"open","ping_status":"open","post_password":"","post_name":"searching-algorithms-in-javascript","to_ping":"","pinged":"","post_modified":"2024-11-14 04:16:56","post_modified_gmt":"2024-11-14 04:16:56","post_content_filtered":"","post_parent":0,"guid":"https:\/\/blogue.tech\/?p=277","menu_order":0,"post_type":"post","post_mime_type":"","comment_count":"0","filter":"raw"}],"next":false,"prev":false,"total_page":1},"paged":1,"column_class":"jeg_col_3o3","class":"jnews_block_3"};
\n- While the left pointer comes before the right pointer:<\/li>\n\n\n\n
- Create a pointer in the middle.<\/li>\n\n\n\n
- If you find the value you want,return the index.<\/li>\n\n\n\n
- If the value is too small,move the left pointer up.<\/li>\n\n\n\n
- If the value is too large,move the right pointer down.<\/li>\n\n\n\n
- If you never find the value,return -1.<\/li>\n<\/ul>\n\n\n\n
var binarySearch = function(arr,elem){\n var start = 0;\n var end = arr.length - 1;\n var middle = Math.floor(start + end \/ 2);\n while(arr[middle] !== elem && start <= end){\n if(elem<arr[middle]){\n end=middle-1;\n }else{\n start = middle+1;\n }\n middle = Math.floor((start+end)\/2)\n }\n \/\/ if(arr[middle] === elem){\/\/ return middle;\/\/ }\/\/ return -1;\nreturn arr[middle] === elem ? middle : -1;\n}\n\n\nconsole.log(binarySearch([2,4,6,9,11,14,20,25,28,40],11)) \n\noutput: 4\n<\/pre>\n\n\n\n3.String Search<\/strong><\/h2>\n\n\n\n
This not totally related to linear search or Binary search. I just wanted to add it here as it is very much important for searching string. A very simple way to search strings is given below:<\/p>\n\n\n\n
Pseudocode:<\/u><\/strong><\/p>\n\n\n\n
\n
- Loop Over the longer string.<\/li>\n\n\n\n
- Loop Over the shorter string.<\/li>\n\n\n\n
- If the characters don't match,break out of the inner loop.<\/li>\n\n\n\n
- If the characters match,Keep going.<\/li>\n\n\n\n
- If you complete the inner loop and find a match, increment the count of matches.<\/li>\n\n\n\n
- Return the count<\/li>\n<\/ul>\n\n\n\n
function naiveSearch(str, word){\n var count = 0;\n for(var i = 0; i < str.length; i++){\n for(var j = 0; j < word.length; j++){\n if(word[j] !== str[i+j]) break;\n if(j === word.length - 1) count++;\n }\n }\n return count;\n}\n\n\nconsole.log(naiveSearch(\"search and find\", \"an\"))\n\noutput: [7]\n<\/pre>\n\n\n\nBut this way we have to search each and every word from the begining in case of multiple data to search.The Knuth-Morris-Pratt string search algorithm<\/a> or KMP algorithm is an algorithm for finding a substring within another string that uses information calculated about the substring to speed up the search process.Before looking through the text to be searched, a table of jump lengths is calculated from the search string. Rather than iterating through the whole string, you can determine how many characters to skip over based on the structure of the word being searched for. As you scan through the search text and you find a mismatch, you can start comparing characters again from the last matching substring between the search term and the search text.E.g. if you are searching through \"Hello world how ya doin?\" for the words \u201cold world new\u201d, every time you find an instance of \u201dold world new\u201d that isn\u2019t followed by a line-break, you can skip the characters of checking the string and restart from the beginning of your words, because you know that they can\u2019t occur again within that span because you have already checked those and they don\u2019t match the begging of the search words. Basically you already know that index is the next occurence of world, so you can start again from there.<\/p>\n\n\n\n
\/\/ Construct a table with table[i] as the length of the longest prefix of the substring 0..i\n\/\/ create a table of size equal to the length of `str`\n\/\/ table[i] will store the prefix of the longest prefix of the substring str[0..i]\n\/\/ the longest prefix of the substring str[0] has length\n\/\/ for the substrings the following substrings, we have two cases\n\/\/ case 1. the current character doesn't match the last character of the longest prefix\n\/\/ if that is the case, we have to backtrack, and try find a character that will be equal to the current character\n\/\/ if we reach 0, then we couldn't find a chracter\n\/\/ case 2. The last character of the longest prefix matches the current character in `str`\n\/\/ if that is the case, we know that the longest prefix at position i has one more character.\n\/\/ for example consider `.` be any character not contained in the set [a.c]\n\/\/ str = abc....abc\n\/\/ consider `i` to be the last character `c` in `str`\n\/\/ maxPrefix = will be 2 (the first `c` in `str`)\n\/\/ maxPrefix now will be 3\n\/\/ so the max prefix for table[9] is 3\nfunction makeTable(str) {\n \n \n var table = new Array(str.length);\n var maxPrefix = 0;\n \n table[0] = 0;\n \n \n for (var i = 1; i < str.length; i++) {\n while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) {\n \n maxPrefix = table[maxPrefix - 1];\n }\n \n if (str.charAt(maxPrefix) === str.charAt(i)) {\n maxPrefix++;\n }\n table[i] = maxPrefix;\n }\n return table;\n }\n \n\/\/ Find all the words that matches in a given string `str`\n\/\/ this algorithm is based on the Knuth\u2013Morris\u2013Pratt algorithm. Its beauty consists in that it performs the matching in O(n)\n\/\/ find the prefix table in O(n)\n\/\/ `j` is the index in `word(P)`\n\/\/ `i` is the index in `str(S)`\n\/\/ Case 1. S[i] == P[j] so we move to the next index in `S` and `P`\n\/\/ Case 2. `j` is equal to the length of `P`\n\/\/ that means that we reached the end of `P` and thus we found a match\n\/\/ Next we have to update `j` because we want to save some time\n\/\/ instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far.\n\/\/ j-1 means the last character of `P` because j is actually `P.length`\n\/\/ e.g.\n\/\/ S = a b a b d e\n\/\/ P = `a b`a b\n\/\/ we will jump to `a b` and we will compare d and a in the next iteration\n\/\/ a b a b `d` e\n\/\/ a b `a` b\n\/\/ Case 3.\n\/\/ S[i] != P[j] There's a mismatch!\n\/\/ if we have found at least a character in common, do the same thing as in case 2\n\/\/ otherwise, j = 0, and we can move to the next character S[i+1]function kmpMatching(str, word) {\n \n var prefixes = makeTable(word);\n var matches = [];\n \n \n var j = 0;\n var i = 0;\n while (i < str.length) {\n \n if (str.charAt(i) === word.charAt(j)) {\n i++;\n j++;\n }\n \n if (j === word.length) {\n matches.push(i-j);\n \n j = prefixes[j-1];\n }\n \n else if (str.charAt(i) !== word.charAt(j)) {\n \n if (j !== 0) {\n j = prefixes[j-1];\n } else {\n \n i++;\n }\n }\n }\n \n return matches;\n }\n\nconsole.log(kmpMatching(\"it implies that it is very important\",\"impo\"))\n\noutput: [27]\n<\/pre>\n\n\n\nWe can implement these algorithms in real world applications.Hope it helps.There are many other algorithms to use. But for a start these might help.<\/p>\n\n\n\n
Happy coding.....<\/p>\n","post_title":"Searching Algorithms in JavaScript","post_excerpt":"The Searching Algorithm can be implemented with other languages as well. But here we will work with JavaScript to solve the Searching Algorithms. These algorithms are used to handle or work with the search related task in our projects or any applications that require searching. Searching is made easier by these algorithms. Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them.","post_status":"publish","comment_status":"open","ping_status":"open","post_password":"","post_name":"searching-algorithms-in-javascript","to_ping":"","pinged":"","post_modified":"2024-11-14 04:16:56","post_modified_gmt":"2024-11-14 04:16:56","post_content_filtered":"","post_parent":0,"guid":"https:\/\/blogue.tech\/?p=277","menu_order":0,"post_type":"post","post_mime_type":"","comment_count":"0","filter":"raw"}],"next":false,"prev":false,"total_page":1},"paged":1,"column_class":"jeg_col_3o3","class":"jnews_block_3"};
\n- Create a left pointer at the start of the array and a right pointer at the end of the array<\/li>\n\n\n\n
- While the left pointer comes before the right pointer:<\/li>\n\n\n\n
- Create a pointer in the middle.<\/li>\n\n\n\n
- If you find the value you want,return the index.<\/li>\n\n\n\n
- If the value is too small,move the left pointer up.<\/li>\n\n\n\n
- If the value is too large,move the right pointer down.<\/li>\n\n\n\n
- If you never find the value,return -1.<\/li>\n<\/ul>\n\n\n\n
var binarySearch = function(arr,elem){\n var start = 0;\n var end = arr.length - 1;\n var middle = Math.floor(start + end \/ 2);\n while(arr[middle] !== elem && start <= end){\n if(elem<arr[middle]){\n end=middle-1;\n }else{\n start = middle+1;\n }\n middle = Math.floor((start+end)\/2)\n }\n \/\/ if(arr[middle] === elem){\/\/ return middle;\/\/ }\/\/ return -1;\nreturn arr[middle] === elem ? middle : -1;\n}\n\n\nconsole.log(binarySearch([2,4,6,9,11,14,20,25,28,40],11)) \n\noutput: 4\n<\/pre>\n\n\n\n3.String Search<\/strong><\/h2>\n\n\n\n
This not totally related to linear search or Binary search. I just wanted to add it here as it is very much important for searching string. A very simple way to search strings is given below:<\/p>\n\n\n\n
Pseudocode:<\/u><\/strong><\/p>\n\n\n\n
\n
- Loop Over the longer string.<\/li>\n\n\n\n
- Loop Over the shorter string.<\/li>\n\n\n\n
- If the characters don't match,break out of the inner loop.<\/li>\n\n\n\n
- If the characters match,Keep going.<\/li>\n\n\n\n
- If you complete the inner loop and find a match, increment the count of matches.<\/li>\n\n\n\n
- Return the count<\/li>\n<\/ul>\n\n\n\n
function naiveSearch(str, word){\n var count = 0;\n for(var i = 0; i < str.length; i++){\n for(var j = 0; j < word.length; j++){\n if(word[j] !== str[i+j]) break;\n if(j === word.length - 1) count++;\n }\n }\n return count;\n}\n\n\nconsole.log(naiveSearch(\"search and find\", \"an\"))\n\noutput: [7]\n<\/pre>\n\n\n\nBut this way we have to search each and every word from the begining in case of multiple data to search.The Knuth-Morris-Pratt string search algorithm<\/a> or KMP algorithm is an algorithm for finding a substring within another string that uses information calculated about the substring to speed up the search process.Before looking through the text to be searched, a table of jump lengths is calculated from the search string. Rather than iterating through the whole string, you can determine how many characters to skip over based on the structure of the word being searched for. As you scan through the search text and you find a mismatch, you can start comparing characters again from the last matching substring between the search term and the search text.E.g. if you are searching through \"Hello world how ya doin?\" for the words \u201cold world new\u201d, every time you find an instance of \u201dold world new\u201d that isn\u2019t followed by a line-break, you can skip the characters of checking the string and restart from the beginning of your words, because you know that they can\u2019t occur again within that span because you have already checked those and they don\u2019t match the begging of the search words. Basically you already know that index is the next occurence of world, so you can start again from there.<\/p>\n\n\n\n
\/\/ Construct a table with table[i] as the length of the longest prefix of the substring 0..i\n\/\/ create a table of size equal to the length of `str`\n\/\/ table[i] will store the prefix of the longest prefix of the substring str[0..i]\n\/\/ the longest prefix of the substring str[0] has length\n\/\/ for the substrings the following substrings, we have two cases\n\/\/ case 1. the current character doesn't match the last character of the longest prefix\n\/\/ if that is the case, we have to backtrack, and try find a character that will be equal to the current character\n\/\/ if we reach 0, then we couldn't find a chracter\n\/\/ case 2. The last character of the longest prefix matches the current character in `str`\n\/\/ if that is the case, we know that the longest prefix at position i has one more character.\n\/\/ for example consider `.` be any character not contained in the set [a.c]\n\/\/ str = abc....abc\n\/\/ consider `i` to be the last character `c` in `str`\n\/\/ maxPrefix = will be 2 (the first `c` in `str`)\n\/\/ maxPrefix now will be 3\n\/\/ so the max prefix for table[9] is 3\nfunction makeTable(str) {\n \n \n var table = new Array(str.length);\n var maxPrefix = 0;\n \n table[0] = 0;\n \n \n for (var i = 1; i < str.length; i++) {\n while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) {\n \n maxPrefix = table[maxPrefix - 1];\n }\n \n if (str.charAt(maxPrefix) === str.charAt(i)) {\n maxPrefix++;\n }\n table[i] = maxPrefix;\n }\n return table;\n }\n \n\/\/ Find all the words that matches in a given string `str`\n\/\/ this algorithm is based on the Knuth\u2013Morris\u2013Pratt algorithm. Its beauty consists in that it performs the matching in O(n)\n\/\/ find the prefix table in O(n)\n\/\/ `j` is the index in `word(P)`\n\/\/ `i` is the index in `str(S)`\n\/\/ Case 1. S[i] == P[j] so we move to the next index in `S` and `P`\n\/\/ Case 2. `j` is equal to the length of `P`\n\/\/ that means that we reached the end of `P` and thus we found a match\n\/\/ Next we have to update `j` because we want to save some time\n\/\/ instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far.\n\/\/ j-1 means the last character of `P` because j is actually `P.length`\n\/\/ e.g.\n\/\/ S = a b a b d e\n\/\/ P = `a b`a b\n\/\/ we will jump to `a b` and we will compare d and a in the next iteration\n\/\/ a b a b `d` e\n\/\/ a b `a` b\n\/\/ Case 3.\n\/\/ S[i] != P[j] There's a mismatch!\n\/\/ if we have found at least a character in common, do the same thing as in case 2\n\/\/ otherwise, j = 0, and we can move to the next character S[i+1]function kmpMatching(str, word) {\n \n var prefixes = makeTable(word);\n var matches = [];\n \n \n var j = 0;\n var i = 0;\n while (i < str.length) {\n \n if (str.charAt(i) === word.charAt(j)) {\n i++;\n j++;\n }\n \n if (j === word.length) {\n matches.push(i-j);\n \n j = prefixes[j-1];\n }\n \n else if (str.charAt(i) !== word.charAt(j)) {\n \n if (j !== 0) {\n j = prefixes[j-1];\n } else {\n \n i++;\n }\n }\n }\n \n return matches;\n }\n\nconsole.log(kmpMatching(\"it implies that it is very important\",\"impo\"))\n\noutput: [27]\n<\/pre>\n\n\n\nWe can implement these algorithms in real world applications.Hope it helps.There are many other algorithms to use. But for a start these might help.<\/p>\n\n\n\n
Happy coding.....<\/p>\n","post_title":"Searching Algorithms in JavaScript","post_excerpt":"The Searching Algorithm can be implemented with other languages as well. But here we will work with JavaScript to solve the Searching Algorithms. These algorithms are used to handle or work with the search related task in our projects or any applications that require searching. Searching is made easier by these algorithms. Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them.","post_status":"publish","comment_status":"open","ping_status":"open","post_password":"","post_name":"searching-algorithms-in-javascript","to_ping":"","pinged":"","post_modified":"2024-11-14 04:16:56","post_modified_gmt":"2024-11-14 04:16:56","post_content_filtered":"","post_parent":0,"guid":"https:\/\/blogue.tech\/?p=277","menu_order":0,"post_type":"post","post_mime_type":"","comment_count":"0","filter":"raw"}],"next":false,"prev":false,"total_page":1},"paged":1,"column_class":"jeg_col_3o3","class":"jnews_block_3"};
\n- Function accepts a sorted array and a value<\/li>\n\n\n\n
- Create a left pointer at the start of the array and a right pointer at the end of the array<\/li>\n\n\n\n
- While the left pointer comes before the right pointer:<\/li>\n\n\n\n
- Create a pointer in the middle.<\/li>\n\n\n\n
- If you find the value you want,return the index.<\/li>\n\n\n\n
- If the value is too small,move the left pointer up.<\/li>\n\n\n\n
- If the value is too large,move the right pointer down.<\/li>\n\n\n\n
- If you never find the value,return -1.<\/li>\n<\/ul>\n\n\n\n
var binarySearch = function(arr,elem){\n var start = 0;\n var end = arr.length - 1;\n var middle = Math.floor(start + end \/ 2);\n while(arr[middle] !== elem && start <= end){\n if(elem<arr[middle]){\n end=middle-1;\n }else{\n start = middle+1;\n }\n middle = Math.floor((start+end)\/2)\n }\n \/\/ if(arr[middle] === elem){\/\/ return middle;\/\/ }\/\/ return -1;\nreturn arr[middle] === elem ? middle : -1;\n}\n\n\nconsole.log(binarySearch([2,4,6,9,11,14,20,25,28,40],11)) \n\noutput: 4\n<\/pre>\n\n\n\n3.String Search<\/strong><\/h2>\n\n\n\n
This not totally related to linear search or Binary search. I just wanted to add it here as it is very much important for searching string. A very simple way to search strings is given below:<\/p>\n\n\n\n
Pseudocode:<\/u><\/strong><\/p>\n\n\n\n
\n
- Loop Over the longer string.<\/li>\n\n\n\n
- Loop Over the shorter string.<\/li>\n\n\n\n
- If the characters don't match,break out of the inner loop.<\/li>\n\n\n\n
- If the characters match,Keep going.<\/li>\n\n\n\n
- If you complete the inner loop and find a match, increment the count of matches.<\/li>\n\n\n\n
- Return the count<\/li>\n<\/ul>\n\n\n\n
function naiveSearch(str, word){\n var count = 0;\n for(var i = 0; i < str.length; i++){\n for(var j = 0; j < word.length; j++){\n if(word[j] !== str[i+j]) break;\n if(j === word.length - 1) count++;\n }\n }\n return count;\n}\n\n\nconsole.log(naiveSearch(\"search and find\", \"an\"))\n\noutput: [7]\n<\/pre>\n\n\n\nBut this way we have to search each and every word from the begining in case of multiple data to search.The Knuth-Morris-Pratt string search algorithm<\/a> or KMP algorithm is an algorithm for finding a substring within another string that uses information calculated about the substring to speed up the search process.Before looking through the text to be searched, a table of jump lengths is calculated from the search string. Rather than iterating through the whole string, you can determine how many characters to skip over based on the structure of the word being searched for. As you scan through the search text and you find a mismatch, you can start comparing characters again from the last matching substring between the search term and the search text.E.g. if you are searching through \"Hello world how ya doin?\" for the words \u201cold world new\u201d, every time you find an instance of \u201dold world new\u201d that isn\u2019t followed by a line-break, you can skip the characters of checking the string and restart from the beginning of your words, because you know that they can\u2019t occur again within that span because you have already checked those and they don\u2019t match the begging of the search words. Basically you already know that index is the next occurence of world, so you can start again from there.<\/p>\n\n\n\n
\/\/ Construct a table with table[i] as the length of the longest prefix of the substring 0..i\n\/\/ create a table of size equal to the length of `str`\n\/\/ table[i] will store the prefix of the longest prefix of the substring str[0..i]\n\/\/ the longest prefix of the substring str[0] has length\n\/\/ for the substrings the following substrings, we have two cases\n\/\/ case 1. the current character doesn't match the last character of the longest prefix\n\/\/ if that is the case, we have to backtrack, and try find a character that will be equal to the current character\n\/\/ if we reach 0, then we couldn't find a chracter\n\/\/ case 2. The last character of the longest prefix matches the current character in `str`\n\/\/ if that is the case, we know that the longest prefix at position i has one more character.\n\/\/ for example consider `.` be any character not contained in the set [a.c]\n\/\/ str = abc....abc\n\/\/ consider `i` to be the last character `c` in `str`\n\/\/ maxPrefix = will be 2 (the first `c` in `str`)\n\/\/ maxPrefix now will be 3\n\/\/ so the max prefix for table[9] is 3\nfunction makeTable(str) {\n \n \n var table = new Array(str.length);\n var maxPrefix = 0;\n \n table[0] = 0;\n \n \n for (var i = 1; i < str.length; i++) {\n while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) {\n \n maxPrefix = table[maxPrefix - 1];\n }\n \n if (str.charAt(maxPrefix) === str.charAt(i)) {\n maxPrefix++;\n }\n table[i] = maxPrefix;\n }\n return table;\n }\n \n\/\/ Find all the words that matches in a given string `str`\n\/\/ this algorithm is based on the Knuth\u2013Morris\u2013Pratt algorithm. Its beauty consists in that it performs the matching in O(n)\n\/\/ find the prefix table in O(n)\n\/\/ `j` is the index in `word(P)`\n\/\/ `i` is the index in `str(S)`\n\/\/ Case 1. S[i] == P[j] so we move to the next index in `S` and `P`\n\/\/ Case 2. `j` is equal to the length of `P`\n\/\/ that means that we reached the end of `P` and thus we found a match\n\/\/ Next we have to update `j` because we want to save some time\n\/\/ instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far.\n\/\/ j-1 means the last character of `P` because j is actually `P.length`\n\/\/ e.g.\n\/\/ S = a b a b d e\n\/\/ P = `a b`a b\n\/\/ we will jump to `a b` and we will compare d and a in the next iteration\n\/\/ a b a b `d` e\n\/\/ a b `a` b\n\/\/ Case 3.\n\/\/ S[i] != P[j] There's a mismatch!\n\/\/ if we have found at least a character in common, do the same thing as in case 2\n\/\/ otherwise, j = 0, and we can move to the next character S[i+1]function kmpMatching(str, word) {\n \n var prefixes = makeTable(word);\n var matches = [];\n \n \n var j = 0;\n var i = 0;\n while (i < str.length) {\n \n if (str.charAt(i) === word.charAt(j)) {\n i++;\n j++;\n }\n \n if (j === word.length) {\n matches.push(i-j);\n \n j = prefixes[j-1];\n }\n \n else if (str.charAt(i) !== word.charAt(j)) {\n \n if (j !== 0) {\n j = prefixes[j-1];\n } else {\n \n i++;\n }\n }\n }\n \n return matches;\n }\n\nconsole.log(kmpMatching(\"it implies that it is very important\",\"impo\"))\n\noutput: [27]\n<\/pre>\n\n\n\nWe can implement these algorithms in real world applications.Hope it helps.There are many other algorithms to use. But for a start these might help.<\/p>\n\n\n\n
Happy coding.....<\/p>\n","post_title":"Searching Algorithms in JavaScript","post_excerpt":"The Searching Algorithm can be implemented with other languages as well. But here we will work with JavaScript to solve the Searching Algorithms. These algorithms are used to handle or work with the search related task in our projects or any applications that require searching. Searching is made easier by these algorithms. Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them.","post_status":"publish","comment_status":"open","ping_status":"open","post_password":"","post_name":"searching-algorithms-in-javascript","to_ping":"","pinged":"","post_modified":"2024-11-14 04:16:56","post_modified_gmt":"2024-11-14 04:16:56","post_content_filtered":"","post_parent":0,"guid":"https:\/\/blogue.tech\/?p=277","menu_order":0,"post_type":"post","post_mime_type":"","comment_count":"0","filter":"raw"}],"next":false,"prev":false,"total_page":1},"paged":1,"column_class":"jeg_col_3o3","class":"jnews_block_3"};
\n\n
- Function accepts a sorted array and a value<\/li>\n\n\n\n
- Create a left pointer at the start of the array and a right pointer at the end of the array<\/li>\n\n\n\n
- While the left pointer comes before the right pointer:<\/li>\n\n\n\n
- Create a pointer in the middle.<\/li>\n\n\n\n
- If you find the value you want,return the index.<\/li>\n\n\n\n
- If the value is too small,move the left pointer up.<\/li>\n\n\n\n
- If the value is too large,move the right pointer down.<\/li>\n\n\n\n
- If you never find the value,return -1.<\/li>\n<\/ul>\n\n\n\n
var binarySearch = function(arr,elem){\n var start = 0;\n var end = arr.length - 1;\n var middle = Math.floor(start + end \/ 2);\n while(arr[middle] !== elem && start <= end){\n if(elem<arr[middle]){\n end=middle-1;\n }else{\n start = middle+1;\n }\n middle = Math.floor((start+end)\/2)\n }\n \/\/ if(arr[middle] === elem){\/\/ return middle;\/\/ }\/\/ return -1;\nreturn arr[middle] === elem ? middle : -1;\n}\n\n\nconsole.log(binarySearch([2,4,6,9,11,14,20,25,28,40],11)) \n\noutput: 4\n<\/pre>\n\n\n\n3.String Search<\/strong><\/h2>\n\n\n\n
This not totally related to linear search or Binary search. I just wanted to add it here as it is very much important for searching string. A very simple way to search strings is given below:<\/p>\n\n\n\n
Pseudocode:<\/u><\/strong><\/p>\n\n\n\n
\n
- Loop Over the longer string.<\/li>\n\n\n\n
- Loop Over the shorter string.<\/li>\n\n\n\n
- If the characters don't match,break out of the inner loop.<\/li>\n\n\n\n
- If the characters match,Keep going.<\/li>\n\n\n\n
- If you complete the inner loop and find a match, increment the count of matches.<\/li>\n\n\n\n
- Return the count<\/li>\n<\/ul>\n\n\n\n
function naiveSearch(str, word){\n var count = 0;\n for(var i = 0; i < str.length; i++){\n for(var j = 0; j < word.length; j++){\n if(word[j] !== str[i+j]) break;\n if(j === word.length - 1) count++;\n }\n }\n return count;\n}\n\n\nconsole.log(naiveSearch(\"search and find\", \"an\"))\n\noutput: [7]\n<\/pre>\n\n\n\n