# 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]);
}
}
}
```

### 11 comments on “CoCubes Programming Question – 3”

• Prachi

n=int(input())
s=[]
for i in range(n):
r=input()
s.append(r)

for i in s:
if len(set(i))==1 :
print(len(i)-1)
else:
if i[:(len(i)//2)]==i[(len(i)//2):]:
print(len(i)//2)

• 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);
}
}
}

• UTSAB

def check(s1, s2):
if(s1 == s2):
return len(s1)
return check(s1[:-1], s2[1:])

t = int(input())
for test in range(t):
s = input()
print(check(s[:-1], s[1:]))

• Aarzoo

/******************************************************************************

Online Java Compiler.
Code, Compile, Run and Debug java program online.
Write your code in this editor and press “Run” button to execute it.

*******************************************************************************/
import java.io.*;
import java.util.*;
import java.util.Map.*;
public class Main
{
public static void main(String[] args) {
//System.out.println(“Hello World”);
String s=”aaab”;
int k=1;
String a=””;
int n=s.length();// String b=””;
String aa=””;
for(k=1;k<s.length()-1;k++)
{
a=s.substring(0,n-k);
aa=s.substring(k,n);
if(a.equals(aa))
{
System.out.println(s.substring(0,n-k)+" "+(n-k));
break;
}

}
if(k==s.length()-1)
System.out.println("-1");
}
}

• Pavan

s=input()
m=len(s)-1
n=0
diff=0
while(m>0 and m<len(s)):
if s[n]==s[m]:
n+=1
m+=1
diff+=1
else:
m-=1
print(diff)

• 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;

}