# 计算一个给定字符串的子字符串，该字符串的变位是回文

2021年4月13日10:25:29 发表评论 622 次浏览

## 本文概述

• 遍历字符串并初始化一个变量X = 0在每个索引。
• 从每个一世的index, 在一系列索引上遍历字符串[i, N – 1], 以及每个字符S [j], 计算按位异或ofX和2(S [j] –‘a’), 在哪里0th一点表示是否一个很奇怪, 1st一点表示是否b是奇数, 等等。
• 然后检查X＆(X – 1)等于0或不。如果发现是真的, 则增加计数by1.

• 完成上述步骤后, 请打印获得的计数。

## C ++

``````//C++ program for the above approach

#include <bits/stdc++.h>
using namespace std;

//Function to print count of substrings
//whose anagrams are palindromic
void countSubstring(string s)
{
int res = 0;

//Iterate over the string
for ( int i = 0;
i <s.length(); i++) {

int x = 0;

for ( int j = i;
j <s.length(); j++) {

//Set the current character
int temp = 1 <<s[j] - 'a' ;

//Parity update
x ^= temp;
if ((x & (x - 1)) == 0)
res++;
}
}

//Print the final count
cout <<res;
}

//Driver Code
int main()
{
string str = "aaa" ;

//Function Call
countSubstring(str);

return 0;
}``````

## Java

``````//Java program for
//the above approach
class GFG{

//Function to print count of subStrings
//whose anagrams are palindromic
static void countSubString(String s)
{
int res = 0 ;

//Iterate over the String
for ( int i = 0 ; i <s.length(); i++)
{
int x = 0 ;
for ( int j = i; j <s.length(); j++)
{
//Set the current character
int temp = 1 <<s.charAt(j) - 'a' ;

//Parity update
x ^= temp;
if ((x & (x - 1 )) == 0 )
res++;
}
}

//Print the final count
System.out.print(res);
}

//Driver Code
public static void main(String[] args)
{
String str = "aaa" ;

//Function Call
countSubString(str);
}
}

//This code is contributed by shikhasingrajput``````

## Python3

``````# Python3 program for
# the above approach

# Function to prcount of subStrings
# whose anagrams are palindromic
def countSubString(s):

res = 0 ;

# Iterate over the String
for i in range ( len (s)):
x = 0 ;
for j in range (i, len (s)):

# Set the current character
temp = 1 <<ord (s[j]) - ord ( 'a' );

# Parity update
x ^ = temp;
if ((x & (x - 1 )) = = 0 ):
res + = 1 ;

# Print final count
print (res);

# Driver Code
if __name__ = = '__main__' :
str = "aaa" ;

# Function Call
countSubString( str );

# This code is contributed by 29AjayKumar``````

## C#

``````//C# program for
//the above approach
using System;
class GFG{

//Function to print count of subStrings
//whose anagrams are palindromic
static void countSubString(String s)
{
int res = 0;

//Iterate over the String
for ( int i = 0; i <s.Length; i++)
{
int x = 0;

for ( int j = i; j <s.Length; j++)
{
//Set the current character
int temp = 1 <<s[j] - 'a' ;

//Parity update
x ^= temp;
if ((x & (x - 1)) == 0)
res++;
}
}

Console.Write(res);
}

//Driver Code
public static void Main(String[] args)
{
String str = "aaa" ;

//Function Call
countSubString(str);
}
}

//This code is contributed by shikhasingrajput``````

``6``

1. 初始化地图以存储蒙版的频率。初始化变量X = 0.
2. 遍历字符串而每一个我th索引, 计算按位异或ofX和2(S [j] –‘a’) 并更新回答通过将当前值的频率相加X在地图中, 因为如果来自0toĴ与的面具相同X, 这是来自的子字符串的掩码0to一世, 然后是子串S [j + 1, i]会有偶数频率<.
3. 同时添加蒙版的频率X xor 2ķ, 在哪里0≤k <26。之后, 增加频率Xby1.
4. 对给定字符串的每个索引重复上述步骤。
5. 遍历给定的字符串后, 打印所需的字符串回答.

## C ++

``````//C++ program for the above approach

#include <bits/stdc++.h>
using namespace std;

//Function to get the count of substrings
//whose anagrams are palindromic
void countSubstring(string s)
{

//Map to store the freq of masks
unordered_map<int , int> m;

//00...00 to 1
m[0] = 1;

//Store mask in x from 0 to i
int x = 0;
for ( int j = 0; j <s.length(); j++) {
x ^= 1 <<(s[j] - 'a' );

for ( int i = 0; i <26; ++i) {
answer += m[x ^ (1 <<i)];
}

//Update frequency
m[x] += 1;
}

}

//Driver Code
int main()
{
string str = "abab" ;

//Function Call
countSubstring(str);
return 0;
}``````

## Java

``````//Java program for
//the above approach
import java.util.*;
class GFG {

//Function to get the count of subStrings
//whose anagrams are palindromic
static void countSubString(String s)
{

//Map to store the freq of masks
HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();

//00...00 to 1
m.put( 0 , 1 );

//Store mask in x from 0 to i
int x = 0 ;
for ( int j = 0 ; j <s.length(); j++)
{
x ^= 1 <<(s.charAt(j) - 'a' );

answer += m.containsKey(x) ? m.get(x) : 0 ;
for ( int i = 0 ; i <26 ; ++i)
{
answer += m.containsKey(x ^ ( 1 <<i)) ?
m.get(x ^ ( 1 <<i)) : 0 ;
}

//Update frequency
if (m.containsKey(x))
m.put(x, m.get(x) + 1 );
else
m.put(x, 1 );
}

}

//Driver Code
public static void main(String[] args)
{
String str = "abab" ;

//Function Call
countSubString(str);
}
}

//This code is contributed by shikhasingrajput``````

## Python3

``````# Python3 program for the above approach
from collections import defaultdict

# Function to get the count of substrings
# whose anagrams are palindromic
def countSubstring(s):

# Map to store the freq of masks
m = defaultdict( lambda : 0 )

# 00...00 to 1
m[ 0 ] = 1

# Store mask in x from 0 to i
x = 0

for j in range ( len (s)):
x ^ = 1 <<( ord (s[j]) - ord ( 'a' ))

for i in range ( 26 ):
answer + = m[x ^ ( 1 <<i)]

# Update frequency
m[x] + = 1

# Driver Code
str = "abab"

# Function call
countSubstring( str )

# This code is contributed by Shivam Singh``````

## C#

``````//C# program for
//the above approach
using System;
using System.Collections.Generic;
class GFG{

//Function to get the count of
//subStrings whose anagrams
//are palindromic
static void countSubString(String s)
{

//Map to store the freq of masks
Dictionary<int , int> m = new Dictionary<int , int>();

//00...00 to 1

//Store mask in x from 0 to i
int x = 0;
for ( int j = 0; j <s.Length; j++)
{
x ^= 1 <<(s[j] - 'a' );

answer += m.ContainsKey(x) ? m[x] : 0;
for ( int i = 0; i <26; ++i)
{
answer += m.ContainsKey(x ^ (1 <<i)) ?
m[x ^ (1 <<i)] : 0;
}

//Update frequency
if (m.ContainsKey(x))
m[x] = m[x] + 1;
else
}

}

//Driver Code
public static void Main(String[] args)
{
String str = "abab" ;

//Function Call
countSubString(str);
}
}

//This code is contributed by shikhasingrajput``````

``7``