水题一道

一说是沙茶题我就都不会做.

没喝过阿..

后缀数组o（n）算法应该可以解决啊。

sa.

算是后缀数组题吧

地板吧？话说用个队列再加个ELFhash？

……我猜的……

澳淄...

搞了半天，终于0msAC了……

看来数据范围还可以再大点……

Orz假傻×

后缀数组的沙茶例题。

建出后缀自动机来，建出sam来，不同子串个数就是每个节点能接受的子串个数=max[u]-min[u]+1=step[u]-step[pre[u]]的总和
<del>请无视代码中求right数组的部分</del>
http://blog.leanote.com/post/okami/vijos1567-%E5%90%8E%E7%BC%80%E8%87%AA%E5%8A%A8%E6%9C%BA

测试数据 #0: Accepted, time = 0 ms, mem = 6232 KiB, score = 5
测试数据 #1: Accepted, time = 0 ms, mem = 6228 KiB, score = 5
测试数据 #2: Accepted, time = 0 ms, mem = 6232 KiB, score = 5
测试数据 #3: Accepted, time = 0 ms, mem = 6228 KiB, score = 5
测试数据 #4: Accepted, time = 0 ms, mem = 6228 KiB, score = 5
测试数据 #5: Accepted, time = 0 ms, mem = 6232 KiB, score = 5
测试数据 #6: Accepted, time = 0 ms, mem = 6232 KiB, score = 5
测试数据 #7: Accepted, time = 0 ms, mem = 6232 KiB, score = 5
测试数据 #8: Accepted, time = 0 ms, mem = 6232 KiB, score = 5
测试数据 #9: Accepted, time = 15 ms, mem = 6232 KiB, score = 5
测试数据 #10: Accepted, time = 0 ms, mem = 6228 KiB, score = 5
测试数据 #11: Accepted, time = 0 ms, mem = 6228 KiB, score = 5
测试数据 #12: Accepted, time = 0 ms, mem = 6228 KiB, score = 5
测试数据 #13: Accepted, time = 0 ms, mem = 6228 KiB, score = 5
测试数据 #14: Accepted, time = 15 ms, mem = 6232 KiB, score = 5
测试数据 #15: Accepted, time = 46 ms, mem = 6228 KiB, score = 5
测试数据 #16: Accepted, time = 31 ms, mem = 6232 KiB, score = 5
测试数据 #17: Accepted, time = 31 ms, mem = 6228 KiB, score = 5
测试数据 #18: Accepted, time = 31 ms, mem = 6228 KiB, score = 5
测试数据 #19: Accepted, time = 31 ms, mem = 6228 KiB, score = 5
Accepted, time = 200 ms, mem = 6232 KiB, score = 100

发一个自认为不错的SuffixArray模板

#include <cstdio>
#include <cstring>
#include <algorithm>

const int maxN=200005;

int suffixArray[maxN]; //1-based
int suffixRank[maxN]; //1-based
int height[maxN]; //LCP length of SA[i] and SA[i-1]

char objStr[maxN];
int objCoded[maxN]; //begin with objCoded[1]
int objLen;

inline int codeChar(char x)
{
return x+1-'a';
} //range:[1..26]

void input()
{
scanf("%d",&objLen);
for(int i=0;i<objLen;i+=80) scanf("%s",objStr+i);

for(int i=1;i<=objLen;i++)
objCoded[i]=codeChar(objStr[i-1]);
objCoded[objLen+1]=-1;
}

const int alphabetSize=26;

int charCount[alphabetSize+1];

int secondKey[maxN]; //use suffixArray[] itself as firstKey
int radixCount[maxN];
int suffixTemp[maxN];

void buildSuffixArray()
{
memset(charCount,0,sizeof(charCount));

for(int i=1;i<=objLen;i++)
++charCount[objCoded[i]];

for(int i=2;i<=alphabetSize;i++)
charCount[i]+=charCount[i-1];

for(int i=1;i<=objLen;i++)
suffixRank[i]=charCount[objCoded[i]];

for(int step=1;step<objLen;step<<=1)
{
for(int i=1;i<=objLen;i++)
secondKey[i]=(i+step<=objLen)?suffixRank[i+step]:0;

memset(radixCount,0,sizeof(radixCount));

for(int i=1;i<=objLen;i++)
++radixCount[secondKey[i]];

for(int i=1;i<=objLen;i++)
radixCount[i]+=radixCount[i-1];

for(int i=objLen;i;i--)
{
int pos=radixCount[secondKey[i]]--;
suffixTemp[pos]=i;
}

memset(radixCount,0,sizeof(radixCount));

for(int i=1;i<=objLen;i++)
++radixCount[suffixRank[i]];

for(int i=1;i<=objLen;i++)
radixCount[i]+=radixCount[i-1];

for(int i=objLen;i;i--)
{
int& cur=suffixTemp[i];
int pos=radixCount[suffixRank[cur]]--;
suffixArray[pos]=cur;
}

int last=suffixRank[suffixArray[1]];
suffixRank[suffixArray[1]]=1;
bool finished=true;

for(int i=2;i<=objLen;i++)
{
int& curPos=suffixArray[i];
int& lastPos=suffixArray[i-1];
int temp=suffixRank[curPos];
if(temp==last && secondKey[curPos]==secondKey[lastPos])
{
suffixRank[curPos]=suffixRank[lastPos];
finished=false;
}
else
suffixRank[curPos]=i;
last=temp;
}

if(finished) break;
}
}

void buildHeight()
{
memset(height,0,sizeof(height));

for(int i=1;i<=objLen;i++)
{
int& curRank=suffixRank[i];
int& lastRank=suffixRank[i-1];
if(curRank>1)
{
height[curRank]=height[lastRank]?height[lastRank]-1:0;
int& lastSA=suffixArray[curRank-1];
int& curSA=suffixArray[curRank]; //curSA=i
for(;;height[curRank]++)
{
if(objCoded[lastSA+height[curRank]] !=
objCoded[curSA+height[curRank]] )
break;
}
}
}
}

typedef long long int64;

#include <iostream>

int main()
{
input();
buildSuffixArray();
buildHeight();

int64 ans=0;

for(int i=1;i<=objLen;i++)
{
ans+=(objLen-suffixArray[i]+1)-height[i];
}

std::cout<<ans<<"\n";
return 0;
}

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 6304 KiB, score = 5
测试数据 #1: Accepted, time = 0 ms, mem = 6300 KiB, score = 5
测试数据 #2: Accepted, time = 0 ms, mem = 6304 KiB, score = 5
测试数据 #3: Accepted, time = 0 ms, mem = 6300 KiB, score = 5
测试数据 #4: Accepted, time = 15 ms, mem = 6300 KiB, score = 5
测试数据 #5: Accepted, time = 0 ms, mem = 6300 KiB, score = 5
测试数据 #6: Accepted, time = 0 ms, mem = 6300 KiB, score = 5
测试数据 #7: Accepted, time = 0 ms, mem = 6300 KiB, score = 5
测试数据 #8: Accepted, time = 0 ms, mem = 6300 KiB, score = 5
测试数据 #9: Accepted, time = 0 ms, mem = 6300 KiB, score = 5
测试数据 #10: Accepted, time = 15 ms, mem = 6300 KiB, score = 5
测试数据 #11: Accepted, time = 0 ms, mem = 6300 KiB, score = 5
测试数据 #12: Accepted, time = 11 ms, mem = 6304 KiB, score = 5
测试数据 #13: Accepted, time = 31 ms, mem = 6300 KiB, score = 5
测试数据 #14: Accepted, time = 15 ms, mem = 6304 KiB, score = 5
测试数据 #15: Accepted, time = 46 ms, mem = 6300 KiB, score = 5
测试数据 #16: Accepted, time = 46 ms, mem = 6300 KiB, score = 5
测试数据 #17: Accepted, time = 46 ms, mem = 6300 KiB, score = 5
测试数据 #18: Accepted, time = 62 ms, mem = 6304 KiB, score = 5
测试数据 #19: Accepted, time = 46 ms, mem = 6304 KiB, score = 5
Accepted, time = 333 ms, mem = 6304 KiB, score = 100

不科学了。。。为什么O（n）的后缀自动机反而比SA O（n log n）的倍增慢额。。。：
编译成功

foo.cpp: In function 'int add_char(int, int)':
foo.cpp:47:1: warning: no return statement in function returning non-void [-Wreturn-type]
测试数据 #0: Accepted, time = 78 ms, mem = 49232 KiB, score = 5
测试数据 #1: Accepted, time = 78 ms, mem = 49236 KiB, score = 5
测试数据 #2: Accepted, time = 93 ms, mem = 49232 KiB, score = 5
测试数据 #3: Accepted, time = 78 ms, mem = 49236 KiB, score = 5
测试数据 #4: Accepted, time = 93 ms, mem = 49228 KiB, score = 5
测试数据 #5: Accepted, time = 62 ms, mem = 49232 KiB, score = 5
测试数据 #6: Accepted, time = 78 ms, mem = 49236 KiB, score = 5
测试数据 #7: Accepted, time = 78 ms, mem = 49236 KiB, score = 5
测试数据 #8: Accepted, time = 78 ms, mem = 49252 KiB, score = 5
测试数据 #9: Accepted, time = 93 ms, mem = 49248 KiB, score = 5
测试数据 #10: Accepted, time = 62 ms, mem = 49296 KiB, score = 5
测试数据 #11: Accepted, time = 46 ms, mem = 49296 KiB, score = 5
测试数据 #12: Accepted, time = 62 ms, mem = 49300 KiB, score = 5
测试数据 #13: Accepted, time = 218 ms, mem = 50584 KiB, score = 5
测试数据 #14: Accepted, time = 234 ms, mem = 50584 KiB, score = 5
测试数据 #15: Accepted, time = 515 ms, mem = 51904 KiB, score = 5
测试数据 #16: Accepted, time = 546 ms, mem = 51908 KiB, score = 5
测试数据 #17: Accepted, time = 515 ms, mem = 51900 KiB, score = 5
测试数据 #18: Accepted, time = 468 ms, mem = 51900 KiB, score = 5
测试数据 #19: Accepted, time = 500 ms, mem = 51904 KiB, score = 5
Accepted, time = 3975 ms, mem = 51908 KiB, score = 100
//***********************************************************************************************
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std ;

#define travel( v ) for ( P p = E[ v ].begin( ) ; p != E[ v ].end( ) ; ++ p )
#define AddEdge( s , t ) E[ s ].push_back( t )

#define P( t ) node[ t ].parent
#define C( t , x ) node[ t ].child[ x ]
#define L( t ) node[ t ].len
#define N( t ) node[ t ]

const int maxn = 201000 ;
const int maxv = maxn << 1 ;

struct Node {
int parent , child[ 26 ] , len ;
Node( ) {
parent = len = 0 ;
memset( child , 0 , sizeof( child ) ) ;
}
} node[ maxv ] ;

int V , last , root ;

void Init_sam( ) {
last = root = maxv - 1 , V = 0 ;
}

int add_char( int c , int l ) {
int p = last , np = ++ V ;
L( V ) = l ;
for ( ; p && ! C( p , c ) ; p = P( p ) ) C( p , c ) = np ;
if ( ! p ) P( np ) = root ; else {
if ( L( p ) + 1 == L( C( p , c ) ) ) P( np ) = C( p , c ) ; else {
int q = C( p , c ) , r = ++ V ;
N( r ) = N( q ) ;
L( r ) = L( p ) + 1 ;
P( q ) = P( np ) = r ;
for ( ; p && C( p , c ) == q ; p = P( p ) ) C( p , c ) = r ;
}
}
last = np ;
}

int getchr( ) {
int ch ;
for ( ch = getchar( ) ; ch < 'a' || ch > 'z' ; ch = getchar( ) ) ;
return ch - 'a' ;
}

int n ;

vector < int > E[ maxv ] ;
typedef vector < int > :: iterator P ;
typedef long long ll ;

ll ans = 0 ;

void dfs( int v , int x ) {
ans += ll( L( v ) - x ) ;
travel( v ) dfs( *p , L( v ) ) ;
}

int main( ) {
Init_sam( ) ;
scanf( "%d" , &n ) ;
for ( int i = 0 ; i ++ < n ; ) {
add_char( getchr( ) , i ) ;
}
for ( int i = 0 ; i ++ < V ; ) AddEdge( P( i ) , i ) ;
dfs( root , 0 ) ;
printf( "%I64d\n" , ans ) ;
return 0 ;
}

额。。。我很水 同SPOJ694

落伍了……

咱还没学后缀数组……

Suffix系列题……