Given a string , find the number of “unordered anagrammatic pairs” of substrings.
Input Format
First line contains , the number of testcases. Each testcase consists of string in one line.
Output Format
For each testcase, print the required answer in one line.
Sample Input#00
2
abba
abcd
Sample Output#00
4
0
Sample Input#01
5
ifailuhkqq
hucpoltgty
ovarjsnrbf
pvmupwjjjf
iwwhrlkpek
Sample Output#01
3
2
2
6
3
Explanation:
abba
a|0,0| a|3,3|
b|1,1| b|2,2|
ab|0,1| ab|2,3|
abb|0,2| abb|1,3|
4
abcd
0
ifailuhkqq
i|0,0| i|3,3|
q|8,8| q|9,9|
afi|0,2| afi|1,3|
3
hucpoltgty
t|6,6| t|8,8|
gt|6,7| gt|7,8|
2
ovarjsnrbf
r|3,3| r|7,7|
jnrs|3,6| jnrs|4,7|
2
pvmupwjjjf
p|0,0| p|4,4|
j|6,6| j|7,7|
j|6,6| j|8,8|
j|7,7| j|8,8|
jj|6,7| jj|7,8|
mpuv|0,3| mpuv|1,4|
6
iwwhrlkpek
w|1,1| w|2,2|
k|6,6| k|9,9|
ekp|6,8| ekp|7,9|
3
Solution using c++
#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; bool check(string str1, string str2); int main() { int numOfCases; int counter = 0; cin >> numOfCases; for (int i = 0; i < numOfCases; i++) { string temp; cin >> temp; int length = temp.length(); for (int subLength = 1; subLength < length; subLength++) { vector <string> subStrings; for (int n = 0; n < length - subLength + 1; n++) subStrings.push_back(temp.substr(n, subLength)); for (int i= 0; i< subStrings.size()-1; i++) { for (int j= i+ 1; j< subStrings.size(); j++) { if (check(subStrings[i], subStrings[j])) counter++; } } } cout << counter << endl; counter = 0; } return 0; } bool check(string str1, string str2) { bool flag = true; if (str1.length() != str2.length()) return false; else { string sortedStr1 = str1; sort(sortedStr1.begin(), sortedStr1.end()); string sortedStr2 = str2; sort(sortedStr2.begin(), sortedStr2.end()); for (int i = 0; i < str1.length(); i++) { if (sortedStr1[i] != sortedStr2[i]) flag = false; } return flag; } }
Advertisements