“强智杯“2020年湖南省大学生计算机程序设计竞赛 D.String Commutativity

本文主要是介绍“强智杯“2020年湖南省大学生计算机程序设计竞赛 D.String Commutativity，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接 https://ac.nowcoder.com/acm/problem/214395

Bobo has n strings s1, … , sn, and he would like to find the number of pairs i < j where si + sj = sj + si.
Note that a + b means the concatenation of the string a and b, i.e., writing the string a first, and the string b second.
输入描述:
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

题意
从n个字符串中找出si,sj两个字符串进行拼接，满足i<j，如果si+sj = sj+si,则为一对，统计有多少对。

思路
我们将字符串化简，比如说aaa可以化简为a，将循环部分去掉，我们还发现只有化简后相同的才满足，那我们就自然做出来了，我们用map<string,int> vis 记录之前个数，每次答案先加，再vis自加。
我们现在唯一问题来了，怎么化简，我们想到可以用next数组来做，通过(len)/(len-nxt[len])来找到循环节，注意不能整除说明没有！这时候子串长度就是len除以循环节，也可以len-nxt[len]加判断求出。

代码

#include <bits/stdc++.h>
typedef long long ll;
const ll mod = 9999999967;
using namespace std;
namespace fastIO {inline void input(int& res) {char c = getchar();res = 0;int f = 1;while (!isdigit(c)) { f ^= c == '-'; c = getchar(); }while (isdigit(c)) { res = (res << 3) + (res << 1) + (c ^ 48);c = getchar(); }res = f ? res : -res;}inline ll qpow(ll a, ll b) {ll ans = 1, base = a;while (b) {if (b & 1) ans = (ans * base % mod +mod )%mod;base = (base * base % mod + mod)%mod;b >>= 1;}return ans;}
}
using namespace fastIO;
const int N = 1e6 + 5;int Case,n,len;
string s;
int nxt[N];void solve(){map<string,int> vis;ll res = 0;for(int i=1;i<=n;i++){cin>>s;len =s.size();int t = len;int j=0,ans,k=-1;len=s.size();nxt[0]=-1;while(j<=len){if(k==-1||s[j]==s[k])nxt[++j]=++k;elsek=nxt[k];}ans = len%(len-nxt[len])?1:len/(len-nxt[len]);s=s.substr(0,len/ans);res += vis[s]; vis[s]++;}printf("%lld\n",res);
}int main(){//init();Case=1;//scanf("%d",&Case);while(~scanf("%d",&n)){solve();}return 0;
}