Microsoft CoCubes Java Programming Question – 3 Longest Prefix Suffix

 

Microsoft  CoCubes Java Programming Question – 3

Longest Prefix Suffix

Given a string of character, find the length of longest proper prefix which is also a proper suffix.

Example:

S = abab

lps is 2 because, ab.. is prefix and ..ab is also a suffix.

Input:

First line is T number of test cases. 1<=T<=100.

Each test case has one line denoting the string of length less than 100000.

Expected time compexity is O(N).

Output:

Print length of longest proper prefix which is also a proper suffix.

Example:

Input:

2

abab

aaaa

Output:

2

3

 

Program :

 

// Microsoft CoCubes Java Programming Question – 3

 

import java.util.*;

import java.lang.*;

import java.io.*;

 

class PreSuf

{

  public static void main (String[]args)

  {

 

    Scanner s = new Scanner (System.in);

    System.out.println("Enter Number of Testcases : ");

    int t = s.nextInt ();

    for (int i = 0; i < t; i++)

      {

            String s1 = s.next ();

            int j = 1, k = 0, l = s1.length (), max = 0, len = 0;

            int lps[] = new int[l];

            while (j < l)

              {

                if (s1.charAt (j) == s1.charAt (len))

                  {

                        len++;

                        lps[j] = len;

                        j++;

                  }

                else

                  {

                        if (len != 0)

                          {

                            len = lps[len - 1];

                          }

                        else

                          {

                            lps[j] = 0;

                            j++;

                          }

                  }

              }

 

            System.out.println (lps[l - 1]);

      }

  }

}

 

For Output check the Video :