偶串

題目描述

一個字元串S是偶串當且僅當S中的每一個字元都出現了偶數次。如字元串”aabccb”是一個偶串，因為字元a,b,c都出現了兩次。而字元串”abbcc”不是偶串，因為字元a出現了一次。

現在給出一個長度為n的字元串T=t1,t2,t3,…,tn。字元串的子串為其中任意連續一段。T長度為1的子串有n個，長度為2的子串有n-1個，以此類推，T一共有n(n+1)/2個子串。給定T，你能算出它有多少個子串是偶串嗎？

輸入

輸入一個字元串T，T中隻有小寫字母。T的長度不超過100000。

樣例輸入

abbc

輸出

輸出一個數，T的所有子串中偶串的個數。

樣例輸出

1

時間限制

C/C++語言：2000MS其它語言：4000MS

記憶體限制

C/C++語言：65536KB其它語言：589824K

解題思路

參考官方思路。這題一看就較為複雜，暴力算法檢索所有子串，判斷為否為偶串時間複雜度太高。先從簡單的問題入手，如果給你一個子串，怎麼樣判斷是否為偶串呢？其實我們并不在乎字母具體出現次數，隻要知道出現的奇偶就可以。那這樣的話，我們可以考慮用26bit的數來代表一個子串的字母出現次數奇偶的狀态，每一位對于着26個字母裡的位數。統計結果如果為零（即都為偶數個）則是偶串。

對于字元串中随意一段子串呢，若起始點分别為L，R。F代表從0點開始的狀态函數(理論上2^25種)，則當F（R）=F（L-1）時，即R，L-1點處的狀态相同時（異或判斷），這[L,R]是偶串。這樣的話，我們可以周遊字元串，記錄不同狀态出現的次數（狀态太多使用map）。統計完後，對于不同狀态出現的次數（假設為n次），那麼這種狀态下的偶串次數可以輕易得到1+2+…+（n-1）。其實，在代碼編寫中可以把偶串計算次數融合到狀态統計過程中去。

重點是：用26位表示不同狀态，狀态對于偶串的影響，以及計算狀态後偶串數量。編碼不難，思路重要。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<map>
using namespace std;
int main(){
 char data[];
 scanf("%s",data);
 int n=strlen(data);
 map<int,int> mp;
 mp[]=;//初始狀态，26個字母全為偶數次狀态為1
 int status=;
 long long res=;
 for(int i=;i<n;i++){
    int x=data[i]-'a';
     status^=(<<x);
     res+=mp[status];//這句很好，每種狀态下的偶串累加。思考時可以把這行代碼省略，想通後累加部分通過這句實作。
     mp[status]++;//統計不同狀态出現的次數
 } 
 cout<<res<<endl;