Google Interview Question
Program ManagersTeam: Only_me
Country: India
Interview Type: Written Test
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace KMP
{
class Program
{
static void Main(string[] args)
{
String s = "abccabccabccabcbaaaaabccabccabcaaaaaaaaa";
String Pattern = "abccabccabca";
FindString(s, Pattern);
Console.Read();
}
static int[] BuildPrefixArray(String pattern)
{
int[] result = new int[pattern.Length + 1];
result[0] = -1;
result[1] = 0;
int k = 0;
for (int i = 2; i < result.Length; i++)
{
while (k > 0 && pattern[k] != pattern[i - 1])
{
k = result[k];
}
if (pattern[k] == pattern[i - 1])
{
k++;
}
result[i] = k;
}
return result;
}
static void FindString(String s, String pattern)
{
int[] prefix = BuildPrefixArray(pattern);
int match = 0;
for (int i = 0; i < s.Length; i++)
{
while (match > 0 && s[i] != pattern[match])
{
match = prefix[match];
}
if (s[i] == pattern[match])
{
match++;
}
if (match == pattern.Length)
{
Console.WriteLine("We found the pair start on the index:" + (i - pattern.Length + 1));
return;
}
}
Console.WriteLine("We did not find the string.");
}
}
}
public class FindPattern {
public static void main (String[] args){
String s = "abccabccabccabcbaaaaabccabccabcaaaaaaaaa";//"AsheesheeshX";
String P = "abccabccabca";//"sheeshX";
int stringLength = s.length();
int offset =0;
int PLength = P.length();
int i = 0,j=0;
while (i<stringLength && j<PLength)
{
if (s.charAt(i)==P.charAt(j)){
offset++;
i++;
if (j < PLength - 1) j++;
// System.out.println(i+","+j+",and offset is "+offset);
}
else {
i = i-offset;
System.out.println(i+","+j+",and offset is "+offset);
i++;
j=0;
offset=0;
}
//
}
if (j==(PLength-1))
System.out.println("Match found");
else
System.out.println("Match not found");
}
}
Knuth-Morris-Pratt (KMP) string matching Algorithm
- algos April 12, 2013