hash+二分求出最长公共前缀
然后马拉车+前缀和计数
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 #include <cmath> 5 #include <algorithm> 6 #include <set> 7 #include <iostream> 8 #include <map> 9 #include <stack> 10 #include <string> 11 #include <vector> 12 #define pi acos(-1.0) 13 #define eps 1e-9 14 #define fi first 15 #define se second 16 #define rtl rt<<1 17 #define rtr rt<<1|1 18 #define bug printf("****** ") 19 #define mem(a,b) memset(a,b,sizeof(a)) 20 #define name2str(x) #x 21 #define fuck(x) cout<<#x" = "<<x<<endl 22 #define f(a) a*a 23 #define sf(n) scanf("%d", &n) 24 #define sff(a,b) scanf("%d %d", &a, &b) 25 #define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c) 26 #define sffff(a,b,c,d) scanf("%d %d %d %d", &a, &b, &c, &d) 27 #define pf printf 28 #define FRE(i,a,b) for(i = a; i <= b; i++) 29 #define FREE(i,a,b) for(i = a; i >= b; i--) 30 #define FRL(i,a,b) for(i = a; i < b; i++)+ 31 #define FRLL(i,a,b) for(i = a; i > b; i--) 32 #define FIN freopen("data.txt","r",stdin) 33 #define gcd(a,b) __gcd(a,b) 34 #define lowbit(x) x&-x 35 using namespace std; 36 typedef long long LL; 37 typedef unsigned long long ULL; 38 const int mod = 1e9 + 7; 39 const int maxn = 2e5 + 10; 40 const int INF = 0x3f3f3f3f; 41 const LL INFLL = 0x3f3f3f3f3f3f3f3fLL; 42 int lens, lent; 43 char s[maxn << 1], t[maxn], ss[maxn << 1]; 44 int d[maxn], r[maxn << 1]; 45 46 int Init() { 47 int len = strlen ( s + 1 ); 48 ss[0] = '$'; 49 ss[1] = '#'; 50 int j = 2; 51 for ( int i = 1; i <= len; i++ ) ss[j++] = s[i], ss[j++] = '#'; 52 ss[j] = ' '; 53 return j; 54 } 55 void Manacher() { 56 int len = Init(); 57 int p, mx = 0; 58 for ( int i = 1; i < len; i++ ) { 59 if ( i < mx ) r[i] = min ( r[2 * p - i], mx - i ); 60 else r[i] = 1; 61 while ( ss[i - r[i]] == ss[i + r[i]] ) r[i]++; 62 if ( mx < i + r[i] ) p = i, mx = i + r[i]; 63 } 64 for ( int i = 2; i < len; i++ ) { 65 if ( ss[i] == '#' && r[i] == 1 ) continue; 66 int x = i / 2 - r[i] / 2 + 1, y = i / 2 + r[i] / 2 - ! ( i & 1 ); 67 d[x]++; 68 d[ ( x + y ) / 2 + 1]--; 69 } 70 } 71 ULL p[maxn], h1[maxn], h2[maxn],seed=131; 72 73 ULL getkey ( ULL *a, int l, int r ) { 74 return ( a[r] - a[l - 1] * p[r - l + 1] ); 75 } 76 bool check ( int len, int P, int lent ) { 77 if ( getkey ( h1, P - len + 1, P ) == getkey ( h2, lent - len + 1, lent ) ) return true; 78 return false; 79 } 80 int main() { 81 p[0] = 1; 82 for ( int i = 1; i < maxn; i++ ) p[i] = p[i - 1] * seed ; 83 while ( ~scanf ( "%s%s", s + 1, t + 1 ) ) { 84 lens = strlen ( s + 1 ); 85 lent = strlen ( t + 1 ); 86 for ( int i = 1; i <= lens; i++ ) d[i] = 0; 87 Manacher(); 88 for ( int i = 1; i <= lens; i++ ) d[i] += d[i - 1]; 89 reverse ( t+1, t + lent+1 ); 90 for ( int i = 1; i <= lens; ++i ) h1[i] = ( h1[i-1] * seed + s[i] ) ; 91 for ( int i = 1; i <= lent; ++i ) h2[i] = ( h2[i-1] * seed + t[i] ) ; 92 LL res = 0; 93 for ( int i = 1; i < lens; ++i ) { 94 if ( s[i] != t[lent] ) continue; 95 int l = 1, r = min ( lent, i+1 ), mid, ans = 0; 96 while ( r >= l ) { 97 mid = ( l + r ) >> 1; 98 if ( check ( mid, i, lent ) ) ans = mid, l = mid + 1; 99 else r = mid - 1; 100 } 101 res += ( LL ) ans * d[i + 1]; 102 } 103 printf ( "%lld ", res ); 104 } 105 }