Nitin Agrawal
Contact -
  • Home
  • Interviews
    • Secret Receipe
    • InterviewFacts
    • Resume Thoughts
    • Daily Coding Problems
    • BigShyft
    • CompanyInterviews >
      • InvestmentBanks >
        • ECS
        • Bank Of America
        • WesternUnion
        • WellsFargo
      • ProductBasedCompanies >
        • CA Technologies
        • Model N India
        • Verizon Media
        • Oracle & GoJek
        • IVY Computec
        • Nvidia
        • ClearWaterAnalytics
        • ADP
        • ServiceNow
        • Pubmatic
        • Expedia
        • Amphora
        • CDK Global
        • CDK Global
        • Epic
        • Sincro-Pune
        • Whiz.AI
        • ChargePoint
      • ServiceBasedCompanies >
        • Altimetrik
        • ASG World Wide Pvt Ltd
        • Paraxel International & Pramati Technologies Pvt Ltd
        • MitraTech
        • Intelizest Coding Round
        • EPAM
    • Interviews Theory
  • Programming Languages
    • Java Script >
      • Tutorials
      • Code Snippets
    • Reactive Programming >
      • Code Snippets
    • R
    • DataStructures >
      • LeetCode Problems
      • AnagramsSet
    • Core Java >
      • Codility
      • Program Arguments OR VM arguments & Environment variables
      • Java Releases
      • Threading >
        • ThreadsOrder
        • ProducerConsumer
        • Finalizer
        • RaceCondition
        • Executors
        • Future Or CompletableFuture
      • Important Points
      • Immutability
      • Dictionary
      • URL Validator
    • Julia
    • Python >
      • Decorators
      • String Formatting
      • Generators_Threads
      • JustLikeThat
    • Go >
      • Tutorial
      • CodeSnippet
      • Go Routine_Channel
      • Suggestions
    • Methodologies & Design Patterns >
      • Design Principles
      • Design Patterns >
        • TemplatePattern
        • Adapter Design Pattern
        • Decorator
        • Proxy
        • Lazy Initialization
        • CombinatorPattern
        • RequestChaining
        • Singleton >
          • Singletons
  • Frameworks
    • Apache Velocity
    • Spring >
      • Spring Boot >
        • CustomProperties
        • ExceptionHandling
        • Issues
      • Quick View
    • Rest WebServices >
      • Interviews
      • Swagger
    • Cloudera BigData >
      • Ques_Ans
      • Hive
      • Apache Spark >
        • ApacheSpark Installation
        • SparkCode
        • Sample1
        • DataFrames
        • RDDs
        • SparkStreaming
        • SparkFiles
    • Integration >
      • Apache Camel
    • Testing Frameworks >
      • JUnit >
        • JUnit Runners
      • EasyMock
      • Mockito >
        • Page 2
      • TestNG
    • Blockchain >
      • Ethereum Smart Contract
      • Blockchain Java Example
    • Microservices >
      • Messaging Formats
      • Design Patterns
    • AWS >
      • Honeycode
    • Dockers >
      • GitBash
      • Issues
  • Databases
    • MySql
    • Oracle >
      • Interview1
      • SQL Queries
    • Elastic Search
  • Random issues
    • TOAD issue
    • Architect's suggestions
  • Your Views

Knuth Morris Pratt Algorithm implementation in Java

Below is the code written to implement the KMP algorithm.
Please let me know if it can further be improved or it needs correction.

/**
 * String search using Knuth Morris Pratt algorithm
 * @author Nitin
 *
 */
public class KMPImpl {

 private static String text = "abxabcabcaby";
 private static String pattern = "abcaby";
 // private static pattern = "aabaabaaa";

 public static void main(String[] args) {
  int foundAt = kmp(text, pattern);

  if(foundAt >= 0)
   System.out.println("Match found at position : " + foundAt);
  else
   System.out.println("Match not Found!!!");
 }

 private static int[] prefSuffPat(String pattern) {

  //  Time Complexity : O(n)
  //  Space Complexity : O(n)
  //  n : length of pattern
  int len = pattern.length();
  int j = 0;
  int i = 1;
  int k = 1;
  int[] val = new int[len];
  val[0] = 0;

  while(i < len) {
   if(i < len && pattern.charAt(j) == pattern.charAt(i)) {
    val[k] = j+1;
    j++;
    i++;
    k++;
   } else if(i < len && pattern.charAt(j) != pattern.charAt(i)) {
    if(j == 0) {
     val[k] = 0;
     i++;
     k++;
     continue;
    }
    j = val[j-1];
    while(j > 0 && pattern.charAt(j) != pattern.charAt(i)) {
     j = val[j-1];
    }
    if(pattern.charAt(j) == pattern.charAt(i)) {
     val[k] = j+1;
     j++;
     i++;
     k++;
    } else {
     val[k] = 0;
     i++;
     k++;
    }
   }
  }
  return val;
 }

 private static int kmp(String text, String pattern) {
  //  Time Complexity : O(m+n)
  //  Space Complexity : O(n)
  //  n : length of pattern
  //  m : length of text
  int foundAt = -1;

  int[] val = prefSuffPat(pattern);
  int lenT = text.length();
  int lenP = pattern.length();

  int j = 0;
  int i = 0;
  boolean forward = false;

  while(i < lenT && j < lenP) {
   if(text.charAt(i) == pattern.charAt(j)) {
    if(j == 0) {
     foundAt = i;
    }
    i++;
    j++;
    forward = false;
   } else if(text.charAt(i) != pattern.charAt(j) && !forward) {
    if(j > 0)
     j = val[j-1];
    forward = true;
    foundAt = i-j;
   } else if(text.charAt(i) != pattern.charAt(j) && forward) {
    i++;
   }
  }

  if(j != lenP) {
   foundAt = -1;
  }

  return foundAt;
 }
}
Powered by Create your own unique website with customizable templates.