This is a very interesting and efficient way to do the thing mentioned in the title, it came in my mind while working on a 2D array problem and I thought of using this to solve the problem of length of a palindromic substr, this algo basically never uses the naive approach of checking a palindrome, but just starts from the vey bottom and goes to the top with the help of the data gathered from the bottom inferences. Although you can make this return the size of the str by checking for the whole string in the very starting of the algo.
There are two implementations, including python and cpp, to be very honest cpp was a big headache cause it makes even simple manipulations of a 2D array so difficult, unlike python, well we can't complain, C is faster... but still Python is better :).
/** Cpp Version **/
int max_length_palin(string s){
/**Returns the max length of any
palindromic substr present in a string**/
int s_size=s.size();
//Make a 2D array for storing the
results of which indices are palindromes
vector<vector<int>> vec(s_size);
//All the substrs of size 1 are
palindromes, so initialize them with 1
for(int i=0;i<s_size;i++){
for(int j=0;j<s_size;j++){
if(i==j){
vec[i].push_back(1);
}else{
vec[i].push_back(0);
}
}cout<<endl;
}
int start_ind=-1,m_size=-1;
//Now all the substrs of size 2 will
//be made 1 if they the two elems are equal
for(int i=0;i<s_size-1;i++){
if(s[i]==s[i+1]){
vec[i][i+1]=1;
start_ind=i;
m_size=2;
}
}
//Displaying the array for making things clear
for(int i=0;i<s_size;i++){
for(int j=0;j<s_size;j++){
cout<<vec[i][j]<<" ";
}cout<<endl;
}
//Till now we have touched substrs with
//size 1 and 2 now for sizes more than that
int k=3;
//We will go till the size of the str(s_size)
while(k<=s_size){
int i=0;
while(i<=s_size-k){
int j;
j=i+k-1;
if(vec[i+1][j-1]==1 && s[i]==s[j]){
vec[i][j]=1;
start_ind=i;
m_size=j+1-i;
}
i+=1;
}
k+=1;
}
cout<<"The max length palindromic substr"
" is "<<s.substr(start_ind,m_size)<<endl;
return m_size;
}
/** Python Version **/
def give_max_efficient(s):
''' Returns the max length
of a palindromic substr
in a string
'''
n=len(s)
if(isPalin(s)):return n
start_ind=0
m_len=-1
ls=[[False for i in range(n)] for j in range(n)]
# print("ls is",ls)
# ls1=[print(elem) for elem in ls]
for i in range(n-1):
ls[i][i]=True
if s[i]==s[i+1]:
ls[i][i+1]=True
start_ind=i
m_len=2
ls[n-1][n-1]=True
k=3
while(k<=n):
# print("k is",k)
i=0
while(i<=n-k):
j=i+k-1
# print("i=",i,"j=",j)
# print("checking ",ls[i+1][j-1],"elements.")
if ls[i+1][j-1]==True and s[i]==s[j]:
# print("[i+1][j-1]==True and [i]==[j],i=",i,"j=",j)
ls[i][j]=True
start_ind=i
if j+1-i>m_len:
m_len=j+1-i
i+=1
k+=1
# print("ls after performing everything is",ls)
ls3=[print(elem) for elem in ls]
# print("The longest palindromic substsring is",s[start_ind:m_len+start_ind])
return m_len
# def circularPalindromes(s):
# Write your code here
def circularPalindromes(s:str)->list[int]:
tmp=""
ans_ls=list()
for i in range(len(s)):
if i==0:tmp=rotate_str(s,0)
if i!=0:tmp=rotate_str(tmp,1)
# print("The tmp_str returned by
#the rotate_str func is ",tmp)
ans_ls.append(give_max_efficient(tmp))
return ans_ls
Comments
Post a Comment