Revolving Digits
Problem's Link
Mean:
给你一个字符串，你可以将该字符串的任意长度后缀截取下来然后接到最前面，让你统计所有新串中有多少种字典序小于、等于、大于原串。
analyse:
KMP的经典题。
首先我们将原串扩展成两倍，算一遍扩展KMP（自匹配），时间复杂度O(n)。
这样一来，我们就得到了eKMP[i]，eKMP[i]代表s[i...len-1]与s的最长公共子串。
为了避免重复子串重复计数，我们先求出s的最小循环节：
int
min_cycle;
for( int i = 1; i <= len; ++ i)
{
if( i +p [ i ] >= len)
{
min_cycle = len % i ? len: i;
break;
}
}
for( int i = 1; i <= len; ++ i)
{
if( i +p [ i ] >= len)
{
min_cycle = len % i ? len: i;
break;
}
}
然后我们只需统计最小循环节以内的字符就可。
当eKMP[i]>=len时，显然是原串，E++;
否则我们只需比较一位就可判断大小，即：比较s[i+eKMP[i]]和s[eKMP[i]]的大小。
为什么只需比较一位?
因为s[0...eKMP[i]-1]和s[i...i+eKMP[i]-1]是相同的，只需判断第一个不相同的位置就可。
Time complexity: O(N)
Source code:
/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-25-21.41
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef __int64( LL);
typedef unsigned __int64( ULL);
const double eps( 1e-8);
const int MAXN = 100020 * 2;
char s1 [ MAXN ], s2 [ 2 ];
/*
* 求a[i...len-1]和b的最长公共前缀有多长。
* 先对b进行自匹配再与a匹配。
* eKMP[i]就是对应答案。
* p[i]是b[i...len-1]和b的最长公共前缀有多长。
*/
int eKMP [ MAXN ],p [ MAXN ];
void E_KMP( char * a , char *b)
{
//自匹配过程
int la = strlen( a ), lb = strlen(b ), j = 0;
while( j < lb &&b [ j ] ==b [ j + 1 ]) ++ j;
p [ 0 ] = lb ,p [ 1 ] = j;
int k = 1;
for( int i = 2; i < lb; ++ i)
{
int Len = k +p [ k ] - 1 , L =p [ i - k ];
if( L < Len - i + 1)
p [ i ] = L;
else
{
j = max( 0 , Len - i + 1);
while( i + j < lb &&b [ i + j ] ==b [ j ]) ++ j;
p [ i ] = j , k = i;
}
}
// b与a的匹配过程
j = 0;
while( j < la && j < lb && a [ j ] ==b [ j ]) ++ j;
eKMP [ 0 ] = j;
k = 0;
for( int i = 1; i < la; ++ i)
{
int Len = k + eKMP [ k ] - 1 , L =p [ i - k ];
if( L < Len - i + 1)
eKMP [ i ] = L;
else
{
j = max( 0 , Len - i + 1);
while( i + j < la && j < lb && a [ i + j ] ==b [ j ]) ++ j;
eKMP [ i ] = j , k = i;
}
}
}
int main()
{
ios_base :: sync_with_stdio( false);
cin . tie( 0);
int t;
scanf( "%d" , & t);
for( int Cas = 1; Cas <= t; ++ Cas)
{
scanf( "%s" , s1);
int len = strlen( s1);
for( int i = 0; i < len; ++ i)
s1 [ i + len ] = s1 [ i ];
s1 [ len << 1 ] = '\0';
E_KMP( s2 , s1); // 我用的是p[]数组,所以和s2无关
int min_cycle;
for( int i = 1; i <= len; ++ i)
{
if( i +p [ i ] >= len)
{
min_cycle = len % i ? len: i;
break;
}
}
int L = 0 , E = 0 , G = 0;
for( int i = 0; i < min_cycle; ++ i)
{
if(p [ i ] >= len) ++ E;
else
{
if( s1 [ i +p [ i ]] > s1 [p [ i ]]) ++ G;
else ++ L;
}
}
printf( "Case %d: %d %d %d \n " , Cas , L , E , G);
}
return 0;
}
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-25-21.41
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef __int64( LL);
typedef unsigned __int64( ULL);
const double eps( 1e-8);
const int MAXN = 100020 * 2;
char s1 [ MAXN ], s2 [ 2 ];
/*
* 求a[i...len-1]和b的最长公共前缀有多长。
* 先对b进行自匹配再与a匹配。
* eKMP[i]就是对应答案。
* p[i]是b[i...len-1]和b的最长公共前缀有多长。
*/
int eKMP [ MAXN ],p [ MAXN ];
void E_KMP( char * a , char *b)
{
//自匹配过程
int la = strlen( a ), lb = strlen(b ), j = 0;
while( j < lb &&b [ j ] ==b [ j + 1 ]) ++ j;
p [ 0 ] = lb ,p [ 1 ] = j;
int k = 1;
for( int i = 2; i < lb; ++ i)
{
int Len = k +p [ k ] - 1 , L =p [ i - k ];
if( L < Len - i + 1)
p [ i ] = L;
else
{
j = max( 0 , Len - i + 1);
while( i + j < lb &&b [ i + j ] ==b [ j ]) ++ j;
p [ i ] = j , k = i;
}
}
// b与a的匹配过程
j = 0;
while( j < la && j < lb && a [ j ] ==b [ j ]) ++ j;
eKMP [ 0 ] = j;
k = 0;
for( int i = 1; i < la; ++ i)
{
int Len = k + eKMP [ k ] - 1 , L =p [ i - k ];
if( L < Len - i + 1)
eKMP [ i ] = L;
else
{
j = max( 0 , Len - i + 1);
while( i + j < la && j < lb && a [ i + j ] ==b [ j ]) ++ j;
eKMP [ i ] = j , k = i;
}
}
}
int main()
{
ios_base :: sync_with_stdio( false);
cin . tie( 0);
int t;
scanf( "%d" , & t);
for( int Cas = 1; Cas <= t; ++ Cas)
{
scanf( "%s" , s1);
int len = strlen( s1);
for( int i = 0; i < len; ++ i)
s1 [ i + len ] = s1 [ i ];
s1 [ len << 1 ] = '\0';
E_KMP( s2 , s1); // 我用的是p[]数组,所以和s2无关
int min_cycle;
for( int i = 1; i <= len; ++ i)
{
if( i +p [ i ] >= len)
{
min_cycle = len % i ? len: i;
break;
}
}
int L = 0 , E = 0 , G = 0;
for( int i = 0; i < min_cycle; ++ i)
{
if(p [ i ] >= len) ++ E;
else
{
if( s1 [ i +p [ i ]] > s1 [p [ i ]]) ++ G;
else ++ L;
}
}
printf( "Case %d: %d %d %d \n " , Cas , L , E , G);
}
return 0;
}
