2018南京ICPCMediocre String Problem 马拉车

hash+二分求出最长公共前缀

然后马拉车+前缀和计数

 #include <cstdio>

 #include <cstring>

 #include <queue>

 #include <cmath>

 #include <algorithm>

 #include <set>

 #include <iostream>

 #include <map>

 #include <stack>

 #include <string>

 #include <vector>

 #define  pi acos(-1.0)

 #define  eps 1e-9

 #define  fi first

 #define  se second

 #define  rtl   rt<<1

 #define  rtr   rt<<1|1

 #define  bug         printf("******\n")

 #define  mem(a,b)    memset(a,b,sizeof(a))

 #define  name2str(x) #x

 #define  fuck(x)     cout<<#x" = "<<x<<endl

 #define  f(a)        a*a

 #define  sf(n)       scanf("%d", &n)

 #define  sff(a,b)    scanf("%d %d", &a, &b)

 #define  sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)

 #define  sffff(a,b,c,d) scanf("%d %d %d %d", &a, &b, &c, &d)

 #define  pf          printf

 #define  FRE(i,a,b)  for(i = a; i <= b; i++)

 #define  FREE(i,a,b) for(i = a; i >= b; i--)

 #define  FRL(i,a,b)  for(i = a; i < b; i++)+

 #define  FRLL(i,a,b) for(i = a; i > b; i--)

 #define  FIN         freopen("data.txt","r",stdin)

 #define  gcd(a,b)    __gcd(a,b)

 #define  lowbit(x)   x&-x

 using namespace std;

 typedef long long  LL;

 typedef unsigned long long ULL;

 const int mod = 1e9 + ;

 const int maxn = 2e5 + ;

 const int INF = 0x3f3f3f3f;

 const LL INFLL = 0x3f3f3f3f3f3f3f3fLL;

 int lens, lent;

 char s[maxn << ], t[maxn], ss[maxn << ];

 int d[maxn], r[maxn << ];

 int Init() {

     int len = strlen ( s +  );

     ss[] = '$';

     ss[] = '#';

     int j = ;

     for ( int i = ; i <= len; i++ ) ss[j++] = s[i], ss[j++] = '#';

     ss[j] = '\0';

     return j;

 }

 void Manacher() {

     int len = Init();

     int p, mx = ;

     for ( int i = ; i < len; i++ ) {

         if ( i < mx ) r[i] = min ( r[ * p - i], mx - i );

         else r[i] = ;

         while ( ss[i - r[i]] == ss[i + r[i]] ) r[i]++;

         if ( mx < i + r[i] ) p = i, mx = i + r[i];

     }

     for ( int i = ; i < len; i++ ) {

         if ( ss[i] == '#' && r[i] ==  ) continue;

         int x = i /  - r[i] /  + , y = i /  + r[i] /  - ! ( i &  );

         d[x]++;

         d[ ( x + y ) /  + ]--;

     }

 }

 ULL p[maxn], h1[maxn], h2[maxn],seed=;

 ULL getkey ( ULL *a, int l, int r ) {

     return ( a[r] - a[l - ] * p[r - l + ] );

 }

 bool check ( int len, int P, int lent ) {

     if ( getkey ( h1, P - len + , P ) == getkey ( h2, lent - len + , lent ) ) return true;

     return false;

 }

 int main() {

     p[] = ;

     for ( int i = ; i < maxn; i++ ) p[i] = p[i - ] * seed  ;

     while ( ~scanf ( "%s%s", s + , t +  ) ) {

         lens = strlen ( s +  );

         lent = strlen ( t +  );

         for ( int i = ; i <= lens; i++ ) d[i] = ;

         Manacher();

         for ( int i = ; i <= lens; i++ ) d[i] += d[i - ];

         reverse ( t+, t + lent+ );

         for ( int i = ; i <= lens; ++i ) h1[i] = ( h1[i-] * seed + s[i] ) ;

         for ( int i = ; i <= lent; ++i ) h2[i] = ( h2[i-] * seed + t[i] ) ;

         LL res = ;

         for ( int i = ; i < lens; ++i ) {

             if ( s[i] != t[lent] ) continue;

             int l = , r = min ( lent, i+ ), mid, ans = ;

             while ( r >= l ) {

                 mid = ( l + r ) >> ;

                 if ( check ( mid, i, lent ) ) ans = mid, l = mid + ;

                 else r = mid - ;

             }

             res += ( LL ) ans * d[i + ];

         }

         printf ( "%lld\n", res );

     }

 }