CoCubes 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


import java.util.*;
import java.lang.*;
import java.io.*;

class PreSuf
{
  public static void main (String[]args)
  {

    Scanner s = new Scanner (System.in);
    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]);
      }
  }
}

7 comments on “CoCubes Programming Question – 3”


  • Anjana

    import java.util.*;
    public class A1{
    public static void main(String args[]) {
    Scanner scan = new Scanner(System.in);
    int T=scan.nextInt();
    for(int k=0;k<T;k++){
    String s=new String();
    s=scan.next();
    int start=0;
    for(int i=1;i<s.length();i++){
    if (s.charAt(start)==s.charAt(i)){
    start+=1;
    }
    else{
    start=0;
    }

    }
    System.out.println(start);
    }
    }
    }


  • shubham

    s = input()
    l = len(s)
    if len(set(s))==1:
    print(l-1)
    else:
    ans = 0
    for i in range (l-2):
    if (s[:i+1] == s[-1-i:]):
    ans = i+1
    print(ans)


  • servesh

    check this out and try……
    #include

    #include

    using namespace std;

    int main()

    {

    string s= “ser7428uhus”;

    int l = s.length();

    int done=0,pr=0;

    cout<<s;

    cout<<l<<" ";

    int i=0,j=l/2;

    //cout<<s.substr(0,j-i)<<" "<<s.substr(j+i,l-1)<<" ";

    while((s.substr(0,j-i)).compare(s.substr(j+i,l-1))!=0&&l%2==0&&i<l/2-1)

    {

    i++;

    }

    while((s.substr(0,j-i)).compare(s.substr(j+i+1,l-1))!=0&&l%2!=0&&i<l/2-1)

    {

    i++;

    }

    cout<<j-i;

    }


  • Mounika

    //we have to break the string from middle and start matching left and right string. If they are equal return size of any one string else try for shorter lengths on both sides.

    class PreSuf {

    static int longestPrefixSuffix(String s)
    {
    int n = s.length();
    int len = 0;
    if(n < 2) {
    return 0;
    }

    int i = n/2;

    while(i < n) {
    if(s.charAt(i) == s.charAt(len)) {
    ++len;
    ++i;
    }
    else
    {
    if(len == 0) { // no prefix
    ++i;
    }
    else
    {
    // search for shorter prefixes
    –len;
    }
    }
    }

    return len;

    }

    // Driver code
    public static void main (String[] args)
    {
    String s = "blablabla";
    System.out.println(longestPrefixSuffix(s));
    }
    }


  • prince

    a=input()
    l=len(a)
    lps=[0]*l
    i=0
    j=1
    while(j<l):
    if(a[i]==a[j]):
    i=i+1
    lps[j]=i
    j=j+1
    else:
    if(i!=0):
    i=lps[i-1]

    else:
    lps[j]=0
    j=j+1
    print(lps[l-1])


    • servesh

      #include

      #include

      using namespace std;

      int main()

      {

      string s= “ser7428uhus”;

      int l = s.length();

      int done=0,pr=0;

      cout<<s;

      cout<<l<<" ";

      int i=0,j=l/2;

      //cout<<s.substr(0,j-i)<<" "<<s.substr(j+i,l-1)<<" ";

      while((s.substr(0,j-i)).compare(s.substr(j+i,l-1))!=0&&l%2==0&&i<l/2-1)

      {

      i++;

      }

      while((s.substr(0,j-i)).compare(s.substr(j+i+1,l-1))!=0&&l%2!=0&&i<l/2-1)

      {

      i++;

      }

      cout<<j-i;

      }