傳送門:【FZU】Problem 2137 奇異字元串
題目分析:枚舉x所在位置,向左右暴力擴充,lcp(L,x+1)>=x-L就累加ans。複雜度是O(nlogn+26*n),複雜度可以這麼證明,假設我們以字母a為中心,那麼不存在字母a的位置最多n-1個,直接枚舉過去就好了,其他字母同理。
my code:
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
#include <math.h>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long LL ;
#define rep( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i )
#define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )
const int MAXN = 100005 ;
char s[MAXN] ;
int t1[MAXN] , t2[MAXN] , c[MAXN] , sa[MAXN] , rank[MAXN] , xy[MAXN] , height[MAXN] ;
int dp[MAXN][18] ;
int logn[MAXN] ;
int n ;
int cmp ( int* r , int a , int b , int d ) {
return r[a] == r[b] && r[a + d] == r[b + d] ;
}
void getHeight ( int n , int k = 0 ) {
For ( i , 0 , n ) rank[sa[i]] = i ;
rep ( i , 0 , n ) {
if ( k ) -- k ;
int j = sa[rank[i] - 1] ;
while ( s[i + k] == s[j + k] ) ++ k ;
height[rank[i]] = k ;
}
}
void build ( int n , int m = 128 ) {
int* x = t1 , *y = t2 ;
rep ( i , 0 , m ) c[i] = 0 ;
rep ( i , 0 , n ) c[x[i] = s[i]] ++ ;
rep ( i , 1 , m ) c[i] += c[i - 1] ;
rev ( i , n - 1 , 0 ) sa[-- c[x[i]]] = i ;
for ( int d = 1 , p = 0 ; p < n ; d <<= 1 , m = p ) {
p = 0 ;
rep ( i , n - d , n ) y[p ++] = i ;
rep ( i , 0 , n ) if ( sa[i] >= d ) y[p ++] = sa[i] - d ;
rep ( i , 0 , m ) c[i] = 0 ;
rep ( i , 0 , n ) c[xy[i] = x[y[i]]] ++ ;
rep ( i , 1 , m ) c[i] += c[i - 1] ;
rev ( i , n - 1 , 0 ) sa[-- c[xy[i]]] = y[i] ;
swap ( x , y ) ;
p = 0 ;
x[sa[0]] = p ++ ;
rep ( i , 1 , n ) x[sa[i]] = cmp ( y , sa[i - 1] , sa[i] , d ) ? p - 1 : p ++ ;
}
getHeight ( n - 1 ) ;
}
void init_RMQ ( int n ) {
For ( i , 1 , n ) dp[i][0] = height[i] ;
logn[1] = 0 ;
For ( i , 2 , n ) logn[i] = logn[i - 1] + ( i == ( i & -i ) ) ;
for ( int j = 1 ; ( 1 << j ) < n ; ++ j ) {
for ( int i = 1 ; i + ( 1 << j ) - 1 <= n ; ++ i ) {
dp[i][j] = min ( dp[i][j - 1] , dp[i + ( 1 << ( j - 1 ) )][j - 1] ) ;
}
}
}
int rmq ( int L , int R ) {
int k = logn[R - L + 1] ;
return min ( dp[L][k] , dp[R - ( 1 << k ) + 1][k] ) ;
}
int lcp ( int a , int b ) {
a = rank[a] , b = rank[b] ;
return a < b ? rmq ( a + 1 , b ) : rmq ( b + 1 , a ) ;
}
void solve () {
LL ans = 0 ;
scanf ( "%s" , s ) ;
n = strlen ( s ) ;
build ( n + 1 ) ;
init_RMQ ( n ) ;
rep ( i , 0 , n ) {
int l = i - 1 , r = i + 1 ;
while ( l >= 0 && r < n ) {
if ( s[l] == s[i] || s[i] == s[r] ) break ;
//printf ( "%c %c %c\n" , s[l] , s[i] , s[r] ) ;
int t = lcp ( l , i + 1 ) ;
//printf ( "%d %d %d %d\n" , t , i - l , i , l ) ;
if ( t >= i - l ) {
ans += ( LL ) ( r - l + 1 ) * ( r - l + 1 ) ;
}
-- l ;
++ r ;
}
}
printf ( "%I64d\n" , ans ) ;
}
int main () {
int T ;
scanf ( "%d" , &T ) ;
For ( i , 1 , T ) solve () ;
return 0 ;
}