## Google Interview Question

Software Engineers**Team:**Search

**Country:**United States

**Interview Type:**In-Person

Robin-Karp O(m+n)

Credit to Tushar Roy, can't add the link

```
private int prime = 101;
public int patternSearch(char[] text, char[] pattern){
int m = pattern.length;
int n = text.length;
long patternHash = createHash(pattern, m - 1);
long textHash = createHash(text, m - 1);
for (int i = 1; i <= n - m + 1; i++) {
if(patternHash == textHash && checkEqual(text, i - 1, i + m - 2, pattern, 0, m - 1)) {
return i - 1;
}
if(i < n - m + 1) {
textHash = recalculateHash(text, i - 1, i + m - 1, textHash, m);
}
}
return -1;
}
private long recalculateHash(char[] str,int oldIndex, int newIndex,long oldHash, int patternLen) {
long newHash = oldHash - str[oldIndex];
newHash = newHash/prime;
newHash += str[newIndex]*Math.pow(prime, patternLen - 1);
return newHash;
}
private long createHash(char[] str, int end){
long hash = 0;
for (int i = 0 ; i <= end; i++) {
hash += str[i]*Math.pow(prime,i);
}
return hash;
}
private boolean checkEqual(char str1[],int start1,int end1, char str2[],int start2,int end2){
if(end1 - start1 != end2 - start2) {
return false;
}
while(start1 <= end1 && start2 <= end2){
if(str1[start1] != str2[start2]){
return false;
}
start1++;
start2++;
}
return true;
}
```

I came up with this solution, which is similar to OP but is a bit more optimized, would this be wrong?

```
public int isSubstring(String s, String x){
int size = x.length();
for(int i = 0; i < s.length() - size+1; i++){
if(s.charAt(i) == x.charAt(0)){
String check = s.substring(i , i+size);
if(check.equals(x)){
return i;
}
}
}
return -1;
}
```

I'm sure it is just O(n) at worst well kinda more like O(n-x) if you account for the size of the string being searched for

Let me know what you guys think!

#include <iostream>

#include <string>

using namespace std;

int* GetLps(string pattern)

{

int size = pattern.length();

int* lps = new int[size];

lps[0] = 0;

for(int i=1; i<size; i++)

{

int length = lps[i-1];

while(length > 0)

{

if(pattern[i] == pattern[length])

{

lps[i] = length + 1;

break;

}

else

{

length = lps[length-1];

}

}

if(length == 0)

{

if(pattern[0] == pattern[i])

{

lps[i] = 1;

}

else

{

lps[i] = 0;

}

}

}

return lps;

}

int SearchIndex(string s, string x)

{

int* lps = GetLps(x);

int i=0;

int j=0;

int length1 = s.length();

int length2 = x.length();

while(i < length1)

{

if(s[i] == x[j] && j == length2-1)

{

return i-length2+1;

}

else if(s[i] == x[j])

{

i++;

j++;

}

else

{

j = lps[j];

i++;

}

}

return -1;

}

int main() {

string s;

cin>>s;

string x;

cin>>x;

cout<<SearchIndex(s, x);

}

```
#include <iostream>
#include <string>
using namespace std;
int* GetLps(string pattern)
{
int size = pattern.length();
int* lps = new int[size];
lps[0] = 0;
for(int i=1; i<size; i++)
{
int length = lps[i-1];
while(length > 0)
{
if(pattern[i] == pattern[length])
{
lps[i] = length + 1;
break;
}
else
{
length = lps[length-1];
}
}
if(length == 0)
{
if(pattern[0] == pattern[i])
{
lps[i] = 1;
}
else
{
lps[i] = 0;
}
}
}
return lps;
}
int SearchIndex(string s, string x)
{
int* lps = GetLps(x);
int i=0;
int j=0;
int length1 = s.length();
int length2 = x.length();
while(i < length1)
{
if(s[i] == x[j] && j == length2-1)
{
return i-length2+1;
}
else if(s[i] == x[j])
{
i++;
j++;
}
else
{
j = lps[j];
i++;
}
}
return -1;
}
int main() {
string s;
cin>>s;
string x;
cin>>x;
//int* lps = GetLps(s);
cout<<SearchIndex(s, x);
}
```

They wanted Naive/KMP solution or SuffixArray/SuffixTree. You could just code any substring and then talk about scalability and very big strings. But your is N*N. Nice hack about tracker. But it N*N.

- coder February 19, 2018