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
Java
Java
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]); } } }
Login/Signup to comment
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)
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);
}
}
}
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:]))
/******************************************************************************
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");
}
}
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)
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)
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;
}
//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));
}
}
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])
#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;
}
Cocubes Coding Questions