አጭሩ ፓሊንድሮም


የችግር ደረጃ ጠንካራ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን አቅርቦት ፋርስት
ሕብረቁምፊ

በአጭሩ የፓሊንደሮሜ ችግር ውስጥ አንድ ሰጥተናል ክር s ርዝመት l. ካልሆነ ግን ፓልመንድሮም እንዲሆን ከፊቱ ቁምፊዎችን ያክሉ። የተሰጠው ሕብረቁምፊ ፓልመንድሮም ለማድረግ የሚያገለግል አነስተኛውን የቁምፊዎች ብዛት ያትሙ።

አጭሩ ፓሊንድሮም

ለምሳሌ

ግብዓት s = abc

ውጤት 2 (ፊትለፊት ሲ እና ለ በመጨመር የፓሊንደሮም ካባክን ያስከትላል)

ግብዓት s = abbaa

ውጤት 1 (ግንባርን በመጨመር የፓሊንደሮም አቢያባ ያስከትላል)

ቀላል ዘዴ

አልጎሪዝም

  1. የ L ርዝመት ሕብረቁምፊን ያስጀምሩ።
  2. ቆጠራውን እና የባንዲራ ተለዋዋጭን ለማከማቸት ኢንቲጀር ተለዋዋጭ ይፍጠሩ። ሁለቱንም ተለዋዋጭዎች እንደ 0 ያስጀምሩ።
  3. ርዝመቱ ከ 0. የበለጠ በሚሆንበት ጊዜ በሕብረቁምፊ በኩል ይጓዙ እና በክርዎ በኩል ይጓዙ እና የክርቱን መሃል እስኪደርሱ ድረስ የመነሻውን ገጸ-ባህሪን ከማለቂያው ቁምፊ ጋር ማወዳደር ይጀምሩ። የአሁኑ ሕብረቁምፊ ፓሊንድሮም ከሆነ የመነሻ ገጸ-ባህሪያቱ ከማብቂያ ገጸ-ባህሪዎች ጋር ተመሳሳይ ከሆኑ የባንዲራ ተለዋዋጭውን እንደ 1 ያዘምኑ እና ቀለበቱን ይሰብሩ
  4. ሌላ የቁጥር ተለዋዋጭውን በ 1 ከፍ ያደርገዋል እና የሕብረቁምፊውን የመጨረሻ ቁምፊ ያስወግዱ።
  5. የባንዲራ ተለዋዋጭ ከ 1 ጋር እኩል ከሆነ የህትመት ብዛት።

አጭሩ ፓሊንደሮምን ለማግኘት የ C ++ ፕሮግራም

#include<bits/stdc++.h> 
using namespace std; 
  
bool isPalindrome(string s){ 
    int l = s.length(); 
    int j; 
      
    for(int i=0, j=l-1; i<=j; i++, j--){ 
        if(s[i] != s[j]) 
            return false; 
    } 
    return true; 
} 
  
int main(){ 
    string s = "abc"; 
    int count = 0, f = 0; 
      
    while(s.length()>0){ 
        if(isPalindrome(s)){ 
            f = 1; 
             break; 
        } 
        else{ 
            count++; 
            s.erase(s.begin() + s.length() - 1); 
        } 
    } 
      
    if(f) 
        cout<<count; 
}
2

የጃቫ ፕሮግራም አጭሩን ፓሊንዶም ለማግኘት

class Palindrome{ 
  
    static boolean isPalindrome(String s){ 
        int l = s.length(); 
  
        for(int i=0, j=l-1; i<=j; i++, j--){ 
            if(s.charAt(i) != s.charAt(j)){ 
                return false; 
            } 
        } 
        return true; 
    } 
  
    public static void main(String[] args){ 
        String s = "abc"; 
        int count = 0, f = 0; 
  
        while(s.length() > 0){ 
            if(isPalindrome(s)){ 
                f = 1; 
                break; 
            } 
            else{ 
                count++; 
  
                s = s.substring(0, s.length() - 1); 
            } 
        } 
  
        if(f == 1){ 
            System.out.println(count); 
        } 
    } 
}
2

ውስብስብነት ትንተና

የጊዜ ውስብስብነት ኦ (ኤል * ኤል) (ኤል የሕብረቁምፊው ርዝመት ነው)

ረዳት ክፍተት ኦ (1) ምክንያቱም የማያቋርጥ ተጨማሪ ቦታ ስለተጠቀምን

ቀልጣፋ ዘዴ

አልጎሪዝም

  1. የ L ርዝመት ሕብረቁምፊን ያስጀምሩ።
  2. የሕብረቁምፊ ተለዋዋጭ ይፍጠሩ እና የመጀመሪያውን ኦርጅናል ጀርባውን በውስጡ ያከማቹ።
  3. የሕብረቶቹን መገጣጠሚያዎች ለማከማቸት ሌላ ገመድ ይፍጠሩ እና የመጀመሪያውን ገመድ እና የተገለበጠ ሕብረቁምፊን በመካከላቸው ልዩ ቁምፊ ካለው ጋር ያከማቹ ፡፡
  4. የኤልፕስ ድርድርን ያስጀምሩ ፡፡
  5. በሕብረቁምፊ በኩል ይጓዙ እና የ lps ድርድር እሴቶችን ያዘምኑ።
  6. የ lps ድርድርን ይመልሱ።

አጭሩ ፓሊንደሮምን ለማግኘት የ C ++ ፕሮግራም

#include <bits/stdc++.h> 
using namespace std; 
  
vector<int> computeLPSArray(string s){ 
    int l = s.length(); 
    vector<int> lps(l); 
  
    int len = 0; 
    lps[0] = 0; 
  
    int i = 1; 
    while(i<l){ 
        if(s[i] == s[len]){ 
            len++; 
            lps[i] = len; 
            i++; 
        } 
        else{ 
            if(len != 0){ 
                len = lps[len-1]; 
            } 
            else{ 
                lps[i] = 0; 
                i++; 
            } 
        } 
    } 
    return lps; 
} 
  
int minChar(string s){ 
    string rev = s; 
    reverse(rev.begin(), rev.end()); 
  
    string concat = s + "$" + rev; 
  
    vector<int> lps = computeLPSArray(concat); 
  
    return(s.length() - lps.back()); 
} 
  
int main(){ 
    string s = "abc"; 
    cout<<minChar(s); 
    return 0; 
}
2

የጃቫ ፕሮግራም አጭሩን ፓሊንዶም ለማግኘት

class Palindrome{ 
  
    public static int[] computeLPSArray(String s){ 
        int l = s.length(); 
        int lps[] = new int[l]; 
        int i = 1, len = 0; 
        lps[0] = 0;
          
        while(i < l){ 
            if(s.charAt(i) == s.charAt(len)){ 
                len++; 
                lps[i] = len; 
                i++; 
            } 
            else{ 
                if(len != 0){ 
                    len = lps[len - 1]; 
                } 
                else{ 
                    lps[i] = 0; 
                    i++; 
                } 
            } 
        } 
        return lps; 
    } 
      
    static int minChar(String s){  
        StringBuilder S = new StringBuilder(); 
        S.append(s); 
          
        String rev = S.reverse().toString(); 
        S.reverse().append("$").append(rev); 
          
        int lps[] = computeLPSArray(S.toString()); 
        return s.length() - lps[S.length() - 1]; 
    } 

    public static void main(String[] args){ 
        String s = "abc"; 
        System.out.println(minChar(s)); 
    } 
}
2

ውስብስብነት ትንተና

የጊዜ ውስብስብነት ኦ (ኤል) (ኤል የሕብረቁምፊው ርዝመት ነው)

ረዳት ክፍተት ኦ (ኤል) ለኤል ቁምፊዎች ተጨማሪ ቦታ ስለተጠቀምን ፡፡

ማጣቀሻዎች