day 12 - Substring Search Problem
Question – Given a text, and a pattern, find whether the given pattern exists in the text or not.
Implement various algorithms
a) Brute Force Search
b) Knuth-Morris-Pratt Algorithm
c) Z Algorithm
d) Rabin Karp Algorithm
e) Boyer Moore Algorithm
Example
input: text: helloworld, substring: hello
output: 0 (index of 'h', where the substring starts)
input: text: helloworld, substring: hop
output: -1
input: text: abcrxyzgf, substring: xyz
output: 4
A) Brute Force Search
JavaScript Implementation
Solution
Substring search can be done using brute force. In this case, the worst case Time Complexity will be O(m.n), m and n are the lengths of string and pattern respectively.
/**
* @author MadhavBahl
* @date 04/01/2018
* In this case, the worst case Time Complexity will be O(m.n),
* m and n are the lengths of string and pattern respectively.
*/
function substringSearch (str, pattern) {
let strLen = str.length,
patLen = pattern.length,
flag = 0;
for (let i=0; i<(strLen-patLen+1); i++) {
if (str[i] === pattern[0]) {
flag = 1;
for (let j=1; j<patLen; j++) {
if (str[i+j] !== pattern[j]) {
flag = 0;
break;
}
}
if (flag === 1) {
console.log (i);
return i;
}
}
}
console.log (-1);
return -1;
}
substringSearch ("helloworld", "world");
substringSearch ("abcrxyzgf", "xyz");
Using Inbuilt JavaScript Methods
Using String.indexOf()
/**
* @author MadhavBahl
* @date 05/01/2018
* METHOD - Using String.indexOf() method
*/
function substringSearch (str, subStr) {
return str.indexOf(subStr);
}
console.log (substringSearch ("helloworld", "world"));
console.log (substringSearch ("abcrxyzgf", "xyz"));
Using String.search()
/**
* @author MadhavBahl
* @date 05/01/2018
* METHOD - Using String.search() method
*/
function substringSearch (str, subStr) {
return str.search (subStr);
}
console.log (substringSearch ("helloworld", "world"));
console.log (substringSearch ("abcrxyzgf", "xyz"));
Python Implementation
Solution
'''
@author prateek3255
@date 05/01/2018
'''
def subStringSearch(string,pattern):
for i in range(len(string)-len(pattern)):
if string[i:i+len(pattern)]==pattern:
return i
return -1
print(subStringSearch("helloworld","hello"))
print(subStringSearch("helloworld","hop"))
print(subStringSearch("abcrxyzgf","xyz"))
C++ Implementation
Solution
/**
* @date 04/01/18
* @author SPREEHA DUTTA
*/
#include <bits/stdc++.h>
using namespace std;
int search(string s,string w)
{
int i,j;int k=-1;int c=0;
int m=w.length();
int n=s.length();
for(i=0;i<=n-m;i++)
{
for(j=0,c=i;j<m;j++,c++)
if(s[c]!=w[j])
break;
if(j==m)
{
k=i;
break;
}
}
return k;
}
int main()
{
string s,w;
getline(cin,s);
getline(cin,w);
int t=search (w,s);
cout<<"\n"<<t<<endl;
}
Java Implementation
Solution
import java.util.Scanner;
/**
* Daily Codes Day 12 -- Substring Search (Brute Force Search)
* @author MadhavBahl
* @date 05/01/2018
*/
public class Bruteforce {
public static void main(String[] args) {
// Take input
Scanner input = new Scanner (System.in);
System.out.print("Enter the string: ");
String str = input.next();
System.out.print("Enter the substrinig to search: ");
String subStr = input.next();
// Search the string
int i, j, flag,
strLen = str.length(),
subStrLen = subStr.length();
for (i=0; i<(strLen-subStrLen+1); i++) {
flag = 1;
if (str.charAt(i) == subStr.charAt(0)) {
for (j=1; j<subStrLen; j++) {
if (str.charAt(i+j) != subStr.charAt(j)) {
flag = 0;
break;
}
}
// If substring is found, print the index
if (flag == 1) {
System.out.println("Substring \"" + subStr + "\" was found in string \"" + str + "\" at index " + i);
System.exit(0);
}
}
}
System.out.println("Substring \"" + subStr + "\" was not found in string \"" + str);
System.exit(0);
}
}
B) Knuth-Morris-Pratt Algorithm
JavaScript Implementation
Solution
To Be Added
Python Implementation
Solution
def kmp(string,pattern):
n=len(string)
m=len(pattern)
lps=calculateLPS(pattern)
i=0
j=0
while i<n:
if pattern[j]==string[i]:
i+=1
j+=1
if j==m:
return i-j
elif i<n and pattern[j]!=string[i]:
if j!=0:
j=lps[j-1]
else:
i+=1
return -1
def calculateLPS(pattern):
lps=[0]*len(pattern)
i=1
lenPat=0
while i<len(pattern):
if pattern[i]==pattern[lenPat]:
lenPat+=1
lps[i]=lenPat
i+=1
else:
if lenPat!=0:
lenPat=lps[lenPat-1]
else:
lps[i]=0
i+=1
return lps
print(kmp("helloworld","hello"))
print(kmp("helloworld","hop"))
print(kmp("ABABDABACDABABCABAB","ABABCABAB"))
Java Implementation
Solution
/**
* @date 06/01/1998
* @author spattk (Sitesh Pattanaik)
*/
import java.util.*;
class StringMatching
{
static int KMPSearch(String text, String subs){
int n = subs.length();
int[] lps = new int[n];
generateLPSArray(lps,subs);
n = text.length();
int m = subs.length();
int i=0,j=0;
while(i<n){
if(text.charAt(i)==subs.charAt(j)){
i++;
j++;
}
if(j==m){
//Pattern Found
return (i-j);
}
else if(i<n && text.charAt(i)!=subs.charAt(j)){
if(j!=0){
j = lps[j-1];
}
else{
i++;
}
}
}
return -1;
}
static void generateLPSArray(int[] lps, String subs)
{
int j = 0;
int i = 1;
int n = subs.length();
while(i<n){
if(subs.charAt(i)==subs.charAt(j)){
j++;
lps[i] = j;
i++;
}
else{
if(j!=0){
j = lps[j-1];
}
else{
lps[i] = 0;
i++;
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String text = sc.next();
String subs = sc.next();
System.out.println(KMPSearch(text,subs));
}
}
C++ Implementation
Solution
/**
* @date 04/01/18
* @author SPREEHA DUTTA
*/
#include <bits/stdc++.h>
using namespace std;
void calc(string w,int m,int p[])
{
int l=0,i=1;p[0]=0;
while(i<m)
{
if(p[i]==p[l])
{
l++;
p[i]=l;
i++;
}
else
{
if(l!=0)
l=p[l-1];
else
{
p[i]=l;
i++;
}
}
}
}
int search(string s,string w)
{
int i=0,j=0;int k=-1;
int m=w.length();
int n=s.length();
int arr[m];
calc(w,m,arr);
while(i<n)
{
if(w[j]==s[i])
{
j++;
i++;
}
if(j==m)
{
k=i-j;
break;
}
else if(i<n && w[j]!=s[i])
{
if(j!=0)
j=arr[j-1];
else
i++;
}
}
return k;
}
int main()
{
string s,w;
getline(cin,s);
getline(cin,w);
int t=search (w,s);
cout<<"\n"<<t<<endl;
}
C) Z Algorithm
JavaScript Implementation
Solution
To Be Added
D) Rabin Karp Algorithm
JavaScript Implementation
Solution
To Be Added
Python Implementation
Solution
'''
@author prateek3255
@date 05/01/2018
'''
def rabinKarp(string,pattern,q=153):
n=len(string)
m=len(pattern)
d=256
h=d**(m-1)%q
p=0
t=0
for i in range(0,m):
p=(d*p+ord(pattern[i]))%q
t=(d*t+ord(string[i]))%q
for i in range(n-m+1):
if p==t and string[i:i+m]==pattern:
return i
if i<(n-m):
t= (d*(t-ord(string[i])*h)+ord(string[i+m]))%q
if t<0:
t+=q
return -1
print(rabinKarp("helloworld","hello"))
print(rabinKarp("helloworld","hop"))
print(rabinKarp("ABABDABACDABABCABAB","ABABCABAB"))
C++ Implementation
Solution
/**
* @date 04/01/18
* @author SPREEHA DUTTA
*/
#include <bits/stdc++.h>
using namespace std;
int search(string s,string w,int q)
{
int i=0,j=0;int k=-1;
int m=w.length();
int n=s.length();
int sc=0,wc=0,h=1;
int d=256;
for(i=0;i<m-1;i++)
h=(h*d)%q;
for(i=0;i<m;i++)
{
wc=(d*wc+w[i])%q;
sc=(d*sc+s[i])%q;
}
for(i=0;i<n-m;i++)
{
if(sc==wc)
{
for(j=0;j<m;j++)
if(s[i+j]!=w[j])
break;
if(j==m)
{
k=i;
break;
}
}
if(i<n-m)
{
sc=(d*(sc-s[i]*h)+s[i+m])%q;
if(sc<0)
sc+=q;
}
}
return k;
}
int main()
{
string s,w;
getline(cin,s);
getline(cin,w);
int t=search (w,s,101);
cout<<"\n"<<t<<endl;
}
E) Boyer Moore Algorithm
JavaScript Implementation
Solution
To Be Added
Python Implementation
Solution
'''
@author prateek3255
@date 05/01/2018
'''
def boyerMoore(string,pattern):
n=len(string)
m=len(pattern)
i=0
while i<=n-m:
k=m-1
j=m+i-1
while string[j]==pattern[k]:
k=k-1
j=j-1
if k==0:
return i
if pattern.rfind(string[j])==-1:
i=j+1
else:
i=max(1,j-pattern.rfind(string[j]))
return -1
print(boyerMoore("helloworld","hello"))
print(boyerMoore("helloworld","hop"))
print(boyerMoore("abcrxyzgf","xyz"))
print(boyerMoore("ABABDABACDABABCABAB","ABABCABAB"))
Have Another solution?
The beauty of programming lies in the fact that there is never a single solution to any problem.
In case you have an alternative way to solve this problem, do contribute to this repository (https://github.com/CodeToExpress/dailycodebase)