NC214395. StringCommutativity
描述
输入描述
The input consists of several test cases terminated by end-of-file.The first line of each test case contains an integer n. The i-th of the following n lines contains a string si.· 1 ≤ n ≤ 105· |si| ≤ 106, si contains only lower case characters.· The sum of strings does not exceed 5×106
输出描述
For each test case, print an integer which denotes the result.
示例1
输入:
2 a ab 2 ab ab 3 a aa aaa
输出:
0 1 3
C++ 解法, 执行用时: 323ms, 内存消耗: 4280K, 提交时间: 2021-11-30 20:53:46
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int N=100010;
typedef long long LL;
string s[N];
bool check(string a,string b){
return a+b==b+a;
}
int main(){
int n;
while(cin>>n){
for(int i=0;i<n;i++){
cin>>s[i];
}
sort(s,s+n);
LL t=1,sum=0;
for(int i=1;i<n;i++){
if(check(s[i],s[i-1])) t++;
else sum+=(t-1)*t/2,t=1;
}
sum+=(t-1)*t/2;
printf("%lld\n",sum);
}
return 0;
}