2020牛客暑期多校训练营（第二场） All with Pairs

题意：给你n个字符串，求出，f(s_i,s_j)的意思是字符串 s_i的前缀和字符串 s_j后缀最长相等部分。

题解：先对所有的字符串后缀hash，用map记录每个hash值（后缀）有多少个一样的。这个地方后缀的 hash 值可以将字符串倒过来求，每次乘以base^ i ，这和字符串正着求每次 t=t *base + s 是一样的，可以想象一下，前后缀相同位置乘base的次数是一样的。然后遍历所有的前缀的hash，在map里找当前 hash 值出现的次数的记录下来，最后把符合条件的长度平方乘以个数加起来，即ans+=mp[hash]* i * i。但是这样会有多算的部分，比如 f("aba","aba")，当遍历到 i=1 的时候，会加上一次，遍历到 i=3 的时候也会加上一次。这时应该选择 i=3的时候加上，把 i=1的时候舍去，这样就要用到kmp算法了，可以看出next[3]=1，只要在 i=3 的时候减去 next[3] 就好了。

 1 #include<bits/stdc++.h>

 2 #define ll long long

 3 #define ull unsigned long long

 4 #define pb push_back

 5 #define ft first

 6 #define sd second

 7 #define pii pair<int,int>

 8 #define pll pair<ll,ll>

 9 using namespace std;

10

11 int nt[1000100];

12 int base=131;

13 const ull mod=998244353;

14 map<ull,int> mp;

15 string s[100100];

16 int res[1000100];

17

18 void kmp_nt(string p)

19 {

20     nt[0]=0;

21     for(int i=1,j=0;i<p.size();i++){

22         while(p[i]!=p[j]&&j) j=nt[j-1];

23         if(p[i]==p[j]) j++;

24         nt[i]=j;

25     }

26 }

27

28 void Hash(string s)

29 {

30     ull t=0,p=1;

31     for(int i=s.size()-1;i>=0;i--){

32         t+=p*(s[i]-'a'+1);

33         p*=base;

34         mp[t]++;

35     }

36 }

37

38 int main()

39 {

40     ios::sync_with_stdio(false);

41     cin.tie(0);

42     cout.tie(0);

43     int n;

44     cin>>n;

45     ll ans=0;

46     for(int i=0;i<n;i++) cin>>s[i],Hash(s[i]);

47     for(int i=0;i<n;i++){

48         ull t=0,p=1;

49         for(int j=0;j<s[i].size();j++){

50             t=t*base+s[i][j]-'a'+1;

51             res[j]=mp[t];

52         }

53         kmp_nt(s[i]);

54         for(int j=0;j<s[i].size();j++){

55             if(nt[j]) res[nt[j]-1]-=res[j];

56         }

57         for(int j=0;j<s[i].size();j++){

58             ans+=res[j]%mod*(j+1)%mod*(j+1)%mod;59             ans%=mod;

60         }

61     }

62     cout<<ans<<endl;

63     return 0;

64 }

巴特西

2020牛客暑期多校训练营（第二场） All with Pairs

最新文章

热门文章

巴特西

2020牛客暑期多校训练营 （第二场） All with Pairs

最新文章

热门文章

2020牛客暑期多校训练营（第二场） All with Pairs