Dada una string S , la tarea es encontrar el número de formas de dividir la string S dada en dos strings palindrómicas no vacías.
Ejemplos:
Entrada: S = “aaaa”
Salida: 4
Explicación:
Posibles divisiones: {“a”, “aaaa”}, {“aa”, “aaa”}, {“aaa”, “aa”}, {“aaaa”, “a”}
Entrada: S = “abacc”
Salida: 1
Explicación:
La única división posible es “aba”, “cc”.
Enfoque ingenuo: el enfoque ingenuo es dividir la string en cada índice posible y verificar si ambas substrings son palindrómicas o no. En caso afirmativo, incremente el recuento para ese índice. Imprime el conteo final .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to check whether the
// substring from l to r is
// palindrome or not
bool isPalindrome(int l, int r,
string& s)
{
while (l <= r) {
// If characters at l and
// r differ
if (s[l] != s[r])
// Not a palindrome
return false;
l++;
r--;
}
// If the string is
// a palindrome
return true;
}
// Function to count and return
// the number of possible splits
int numWays(string& s)
{
int n = s.length();
// Stores the count
// of splits
int ans = 0;
for (int i = 0;
i < n - 1; i++) {
// Check if the two substrings
// after the split are
// palindromic or not
if (isPalindrome(0, i, s)
&& isPalindrome(i + 1,
n - 1, s)) {
// If both are palindromes
ans++;
}
}
// Print the final count
return ans;
}
// Driver Code
int main()
{
string S = "aaaaa";
cout << numWays(S);
return 0;
}
Java
// Java program to implement
// the above approach
class GFG{
// Function to check whether the
// substring from l to r is
// palindrome or not
public static boolean isPalindrome(int l, int r,
String s)
{
while (l <= r)
{
// If characters at l and
// r differ
if (s.charAt(l) != s.charAt(r))
// Not a palindrome
return false;
l++;
r--;
}
// If the string is
// a palindrome
return true;
}
// Function to count and return
// the number of possible splits
public static int numWays(String s)
{
int n = s.length();
// Stores the count
// of splits
int ans = 0;
for(int i = 0; i < n - 1; i++)
{
// Check if the two substrings
// after the split are
// palindromic or not
if (isPalindrome(0, i, s) &&
isPalindrome(i + 1, n - 1, s))
{
// If both are palindromes
ans++;
}
}
// Print the final count
return ans;
}
// Driver Code
public static void main(String args[])
{
String S = "aaaaa";
System.out.println(numWays(S));
}
}
// This code is contributed by SoumikMondal
Python3
# Python3 program to implement # the above approach # Function to check whether the # substring from l to r is # palindrome or not def isPalindrome(l, r, s): while (l <= r): # If characters at l and # r differ if (s[l] != s[r]): # Not a palindrome return bool(False) l += 1 r -= 1 # If the string is # a palindrome return bool(True) # Function to count and return # the number of possible splits def numWays(s): n = len(s) # Stores the count # of splits ans = 0 for i in range(n - 1): # Check if the two substrings # after the split are # palindromic or not if (isPalindrome(0, i, s) and isPalindrome(i + 1, n - 1, s)): # If both are palindromes ans += 1 # Print the final count return ans # Driver Code S = "aaaaa" print(numWays(S)) # This code is contributed by divyeshrabadiya07
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to check whether the
// substring from l to r is
// palindrome or not
public static bool isPalindrome(int l, int r,
string s)
{
while (l <= r)
{
// If characters at l and
// r differ
if (s[l] != s[r])
// Not a palindrome
return false;
l++;
r--;
}
// If the string is
// a palindrome
return true;
}
// Function to count and return
// the number of possible splits
public static int numWays(string s)
{
int n = s.Length;
// Stores the count
// of splits
int ans = 0;
for(int i = 0; i < n - 1; i++)
{
// Check if the two substrings
// after the split are
// palindromic or not
if (isPalindrome(0, i, s) &&
isPalindrome(i + 1, n - 1, s))
{
// If both are palindromes
ans++;
}
}
// Print the final count
return ans;
}
// Driver Code
public static void Main(string []args)
{
string S = "aaaaa";
Console.Write(numWays(S));
}
}
// This code is contributed by Rutvik
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to check whether the
// substring from l to r is
// palindrome or not
function isPalindrome(l, r, s)
{
while (l <= r)
{
// If characters at l and
// r differ
if (s[l] != s[r])
// Not a palindrome
return false;
l++;
r--;
}
// If the string is
// a palindrome
return true;
}
// Function to count and return
// the number of possible splits
function numWays(s)
{
let n = s.length;
// Stores the count
// of splits
let ans = 0;
for(let i = 0; i < n - 1; i++)
{
// Check if the two substrings
// after the split are
// palindromic or not
if (isPalindrome(0, i, s) &&
isPalindrome(i + 1, n - 1, s))
{
// If both are palindromes
ans++;
}
}
// Print the final count
return ans;
}
let S = "aaaaa";
document.write(numWays(S));
</script>
Producción:
4
Complejidad de tiempo: O(N 2 )
Enfoque eficiente: El enfoque anterior se puede optimizar usando el algoritmo Hashing y Rabin-Karp para almacenar hashes de prefijo y sufijo de la string. Siga los pasos a continuación para resolver el problema:
- Calcule el hash de prefijo y sufijo de la string dada.
- Para cada índice i en el rango [1, N – 1], verifique si las dos substrings [0, i – 1] y [i, N – 1] son palíndromos o no.
- Para verificar si una substring [l, r] es un palíndromo o no, simplemente verifique:
PrefixHash[l - r] = SuffixHash[l - r]
- Por cada índice i para el que se encuentre que dos substrings son palindrómicas, aumente la cuenta .
- Imprime el valor final de count .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include
using namespace std;
// Modulo for rolling hash
const int MOD = 1e9 + 9;
// Small prime for rolling hash
const int P = 37;
// Maximum length of string
const int MAXN = 1e5 + 5;
// Stores prefix hash
vector prefixHash(MAXN);
// Stores suffix hash
vector suffixHash(MAXN);
// Stores inverse modulo
// of P for prefix
vector inversePrefix(MAXN);
// Stores inverse modulo
// of P for suffix
vector inverseSuffix(MAXN);
int n;
int power(int x, int y, int mod)
{
// Function to compute
// power under modulo
if (x == 0)
return 0;
int ans = 1;
while (y > 0) {
if (y & 1)
ans = (1LL * ans * x)
% MOD;
x = (1LL * x * x) % MOD;
y >>= 1;
}
return ans;
}
// Precompte hashes for the
// given string
void preCompute(string& s)
{
int x = 1;
for (int i = 0; i 0)
prefixHash[i]
= (prefixHash[i]
+ prefixHash[i - 1])
% MOD;
// Compute inverse modulo
// of P ^ i for division
// using Fermat Little theorem
inversePrefix[i] = power(x, MOD - 2,
MOD);
x = (1LL * x * P) % MOD;
}
x = 1;
// Calculate suffix hash
for (int i = n - 1; i >= 0; i--) {
// Calculate and store hash
suffixHash[i]
= (1LL * int(s[i]
- 'a' + 1)
* x)
% MOD;
if (i 0
? prefixHash[l - 1]
: 0);
h = (h + MOD) % MOD;
h = (1LL * h * inversePrefix[l])
% MOD;
return h;
}
// Function to return Suffix
// Hash of substring
int getSuffixHash(int l, int r)
{
// Calculate suffix hash
// from l to r
int h = suffixHash[l]
- (r < n - 1
? suffixHash[r + 1]
: 0);
h = (h + MOD) % MOD;
h = (1LL * h * inverseSuffix[r])
% MOD;
return h;
}
int numWays(string& s)
{
n = s.length();
// Compute prefix and
// suffix hashes
preCompute(s);
// Stores the number of
// possible splits
int ans = 0;
for (int i = 0;
i < n - 1; i++) {
int preHash = getPrefixHash(0, i);
int sufHash = getSuffixHash(0, i);
// If the substring s[0]...s[i]
// is not palindromic
if (preHash != sufHash)
continue;
preHash = getPrefixHash(i + 1,
n - 1);
sufHash = getSuffixHash(i + 1,
n - 1);
// If the substring (i + 1, n - 1)
// is not palindromic
if (preHash != sufHash)
continue;
// If both are palindromic
ans++;
}
return ans;
}
// Driver Code
int main()
{
string s = "aaaaa";
int ans = numWays(s);
cout << ans << endl;
return 0;
}
Producción:
4
Complejidad de tiempo: O(N * log(10 9 ))
Complejidad de espacio: O(N)
Publicación traducida automáticamente
Artículo escrito por insiderpants y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA