Processing math: 100%
Good pairs - MarisaOJ: Marisa Online Judge

Good pairs

Time limit: 1000 ms
Memory limit: 256 MB
Given 2 strings S,T of equal length. Let: Ta=T1T2...Ti Tb=Ti+1Ti+2...Tj Tc=Tj+1Tj+2...Tn and |Ta|,|Tb|,|Tc|>0 A pair i<j is called good if Ta,Tb,Tc can be rearranged to form a new string T′=S. Count the number of good pairs. ### Input - The first line contains string S. - The second line contains string T. ### Output - Print the number of good pairs. ### Constraints - 1≤|S|=|T|≤5000. ### Example Input: aaabaaba Output: 2