वर्णों की न्यूनतम संख्या एक स्ट्रिंग के अंत में सम्मिलित करने के लिए यह विलोमपद बनाने के लिए

Question

सवाल this--

हम वर्णों की न्यूनतम संख्या अंत के कम से सम्मिलित करने के लिए खोजने के लिए की तरह है इसे एक पालिंड्रोम बनाने के लिए एक स्ट्रिंग।

तो, इस समस्या को करने के अपने प्रयासों में, मुझे लगा कि यह सबसे बड़ा पालिंड्रोमिक सबस्ट्रिंग खोजने के बराबर है जो स्ट्रिंग का एक प्रत्यय भी है।

मैं इसे ओ (एन^2) में आसानी से कर सकता हूं लेकिन मैं ओ (एन) समाधान की तलाश में हूं जो संशोधित केएमपी का उपयोग कर संभवतः संभव है। कृपया मुझे समझने में मदद करें।

Answer 1

मेरे पास एक दृष्टिकोण है जो हैशिंग को here उत्तर के रूप में पोस्ट किया गया है।

आप वास्तव में केएमपी का भी उपयोग कर सकते हैं। आप उलट स्ट्रिंग के लिए prefix function गणना कर सकता है, और फिर बाएं से दाएं अपने प्रारंभिक स्ट्रिंग पुनरावृति:

KMP एक समारोह prefix[i] = longest prefix of the string that is a suffix of string[1..i]

हालांकि, हमें पता करने के लिए the longest suffix of our string that is a prefix of the reversed string चाहते गणना करता है। क्यूं कर? अगर हमने:

15232 => reverse = 23251 

फिर स्ट्रिंग उलट तार का एक उपसर्ग है कि सबसे लंबे समय तक प्रत्यय 232 है। यह एक पालिंड्रोम है, और यह आपको जो कुछ पूछ रहा है उसे ढूंढने देता है क्योंकि स्ट्रिंग का एक प्रत्यय उल्टा स्ट्रिंग के उपसर्ग को ओवरलैप करता है यदि दोनों palindromes हैं।

आप मामलों है:

prefix[i] = length - i => you can get a palindrome of 
      length 2*prefix[i] centered at i and i+1 

prefix[i] = length - i + 1 => you can get a palindrome of 
      length 2*prefix[i] - 1 centered at i 

prefix[i] < length - i => you can't have a palindrome, ignore this position 

तो यह KMP एल्गोरिथ्म के उपसर्ग समारोह गणना करने के लिए पर्याप्त होता है।

Answer 2

एक साधारण कोड वर्णों की न्यूनतम संख्या डालने और वापसी के लिए उन्हें दिए गए स्ट्रिंग एक pallindrome

#include <bits/stdc++.h> 
using namespace std; 
bool isPalin(char *s,int x,int l) 
{ 
    for(int i=x,j=l-1;i<j;i++,j--) 
     if(s[i]!=s[j]) 
      return 0; 
    return 1; 
} 
char * f(char *s) 
{ 
    // if s is NULL return NULL 
    if(!s) 
     return NULL; 
    int i,l,j; 
    l=strlen(s); 
    for(i=0;i<l;i++) 
    { 
     // check if string is pallindrome from [i...l-1] 
     if(isPalin(s,i,l) == 1) 
      break; 
    } 
    // if s is already a pallindrome return NULL 
    if(i==0) 
     return NULL; 
    int k=0; 
    // make a char* 
    char *ans = new char[i+1]; 
    for(i-=1;i>=0;i--) 
     ans[k++]=s[i]; 
    ans[k++]='\0'; 
    return ans; 
} 

int main() { 
    char *a = "wxytabbat"; 
    cout<<f(a)<<"\n"; 
    return 0; 
}