/**
*³ÌÐòÔ±±à³ÌÒÕÊõµÚÒ»~¶þÊ®ÆßÕ¼¯½õÓë×ܽᣨ½ÌÄãÈçºÎ±à³Ì)
*
*
*
*/
#include
#include
#include
#include
#include
#include
#include
using namespace std;
/**
*µÚÒ»ÕÂ.×óÐý×Ö·û´®
*
*/
void ReverseOrder(char *pcStr, int nLen)
{
char c = NULL;
int nLow, nHigh;
nLow = 0;
nHigh = nLen - 1;
while (nLow < nHigh)
{
c = pcStr[nLow];
pcStr[nLow] = pcStr[nHigh];
pcStr[nHigh] = c;
++nLow;
--nHigh;
}
}
//Èý´ÎÄæÐò
void RotateString1(char *pcStr, int k, int nSize)
{
ReverseOrder(pcStr, k);
ReverseOrder(pcStr + k, 4);
ReverseOrder(pcStr, nSize);
}
int gcd(int n, int m)
{
int r;
if (n < m)
{
r = n;
n = m;
m = r;
}
while ((r = m%n) != 0)
{
m = n;
n = r;
}
return n;
}
//ÔËÓÃ(j + i*m)%n (j = 0-gcd(n,m), i = 0-(n/gcd(n,m) - 1))
void RotateString2(string &str, int m)
{
int nStrLen, nGcd, nElemInSub, j, i;
nStrLen = str.length();
nGcd = gcd(nStrLen, m);
nElemInSub = nStrLen/nGcd;
for (j = 0; j < nGcd; ++j)
{
char Tmp = str[j];
for (i = 0; i < nElemInSub - 1; ++i)
{
str[(j + i*m)%nStrLen] = str[(j + (i+1)*m)%nStrLen];
}
str[(j + i*m)%nStrLen] = Tmp;
}
}
/**
*µÚ¶þÕÅ.×Ö·û´®ÊÇ·ñ°üº¬¼°Ïà¹ØÎÊÌâÀ©Õ¹
*
*/
/*
*¼ÙÉèÕâÓÐÒ»¸ö¸÷ÖÖ×Öĸ×é³ÉµÄ×Ö·û´®£¬¼ÙÉèÕ⻹ÓÐÁíÍâÒ»¸ö×Ö·û´®£¬
*¶øÇÒÕâ¸ö×Ö·û´®ÀïµÄ×ÖĸÊýÏà¶ÔÉÙһЩ¡£´ÓËã·¨Êǽ²£¬
*ʲô·½·¨ÄÜ×î¿ìµÄ²é³öËùÓÐС×Ö·û´®ÀïµÄ×ÖĸÔÚ´ó×Ö·û´®ÀﶼÓУ¿
*
*/
int IsExistEveryChar1(string &ls, string &ss)
{
int i, index, nums = 0;
int nArray[26] = {0};
for (i = 0; i < ss.length(); ++i)
{
index = ss[i] - 'A';
if (nArray[index] == 0)
{
nArray[index] = 1;
++nums;
}
}
for (i = 0; i < ls.length(); ++i)
{
index = ls[i] - 'A';
if (nArray[index] == 1)
{
if (--nums == 0) break;
}
}
return (i < ls.length()) ?0:-1;
}
//ÿ¸ö×Ö·û¶ÔÓ¦Ò»¸öËØÊý
int IsExistEveryChar2(string &ls, string &ss)
{
int i, index;
int primeNumber[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
long long product = 1;
for (i = 0; i < ls.length(); ++i)
{
index = ls[i] - 'A';
product *= primeNumber[index];
}
for (i = 0; i < ss.length(); ++i)
{
index = ss[i] - 'A';
if (product % primeNumber[index] != 0) return -1;
}
return 0;
}
/**
*×Ö·û´®Æ¥Åäe.g: ABCDE--CD
*/
char* MyStrStr(char *pcStr, char *pcSubStr)
{
char *p = NULL, *pSub = NULL;
p = pcStr;
pSub = pcSubStr;
while (*p != '\0' && *pSub != '\0')
{
if (*p == *pSub)
{
++p;
++pSub;
}
else
{
p -= (pSub - pcSubStr - 1);
pSub = pcSubStr;
}
}
return (*pSub == '\0')? p - strlen(pcSubStr): NULL;
}
/**
*×Ö·û´®¿½±´
*/
char* mystrcpy(char *pcDest, const char *pcSrc)
{
if (pcSrc == NULL || pcDest == NULL) return NULL;
char *pcAddr = pcDest;
while ((*pcDest++ = *pcSrc++) != '\0');
return pcAddr;
}
/**
*×Ö·û´®È«ÅÅÁÐ
*
*/
void SwapChar(char *pcDest, char *pcSrc)
{
char tmp;
if (pcDest == NULL || pcSrc == NULL) return;
tmp = *pcSrc;
*pcSrc = *pcDest;
*pcDest = tmp;
}
void StrArrange(char *pcStr, char *pcBegin)
{
if (*pcBegin == '\0')
{
cout << pcStr << " ";
return;
}
for (char *pcPos = pcBegin; *pcPos != '\0'; ++pcPos)
{
SwapChar(pcBegin, pcPos);
StrArrange(pcStr, pcBegin + 1);
SwapChar(pcBegin, pcPos);
}
}
/**
*×Ö·û´®µÄËùÓÐ×éºÏ
*/
void StrCombination(char *pcStr, char *pcDest)
{
char acDest1[32] = {0}, acDest2[32] = {0};
if (*pcStr == '\0')
{
cout << pcDest << " ";
return;
}
strcpy_s(acDest1, pcDest);
strcpy_s(acDest2, pcDest);
acDest1[strlen(acDest1)] = *pcStr;
StrCombination(pcStr+1, acDest1);
StrCombination(pcStr+1, acDest2);
}
/**
*µÚÈýÕÂ.topkÎÊÌâ
*
*/
//¿ìËÙÅÅÐòµÄÒ»´Î»®·Ö(Ñ¡ÔñµÚÒ»¸öÔªËØ×÷Ϊ»®·ÖÖµ)
int Partition(int *pnArray, int nBegin, int nEnd)
{
int nValue;
nValue = pnArray[nBegin];
while (nBegin < nEnd)
{
while (pnArray[nEnd] >= nValue) --nEnd;
pnArray[nBegin] = pnArray[nEnd];
while (pnArray[nBegin] <= nValue) ++nBegin;
pnArray[nEnd] = pnArray[nBegin];
}
pnArray[nBegin] = nValue;
return nBegin;
}
int SwapInt(int *p, int *q)
{
int tmp;
if (p == NULL || q == NULL) return -1;
tmp = *p;
*p = *q;
*q = tmp;
return 0;
}
//Ëæ»ú»®·Ö
int RandomizedPartition(int *pnArray, int nBegin, int nEnd)
{
int nRand;
srand(time(NULL));
nRand = (rand()%(nEnd - nBegin)) + nBegin;
SwapInt(pnArray, pnArray + nRand);
return Partition(pnArray, nBegin, nEnd);
}
//Ëæ»úÑ¡ÔñµÚKСµÄÔªËØ
int RandomizedSelect(int *pnArray, int nBegin, int nEnd, int k)
{
int q;
if (nBegin > nEnd) return -1;
if (nBegin == nEnd) return pnArray[nBegin];
q = RandomizedPartition(pnArray, nBegin, nEnd);
if (k == q) return pnArray[q];
else if (k < q) return RandomizedSelect(pnArray, nBegin, q - 1, k);
else if (k > q) return RandomizedSelect(pnArray, q + 1, nEnd, k - q);
return -1;
}
void printarray(int *pnArray, int size)
{
int i;
for (i = 0; i < size; ++i)
{
cout << pnArray[i] << " ";
}
cout << endl;
}
//ÓöÑÅÅÐòµÃµ½×îСµÄK¸öÊý
void HeapAdjust(int *pnArray, int i, int size)
{
int child, tmp;
for (tmp = pnArray[i]; 2*i + 1 < size; i = child)
{
child = 2 * i + 1;
if (child < size-1 && pnArray[child] > pnArray[child + 1]) ++child;
if (tmp > pnArray[child]) pnArray[i] = pnArray[child];
else break;
pnArray[child] = tmp;
}
}
void MakeMinHeap(int *pnArray, int size)
{
int i;
for (i = size/2; i >= 0; --i)
{
HeapAdjust(pnArray, i, size);
}
}
int GetHeapMin(int *pnArray, int size, int k)
{
int i, h, min, tmp, child;
min = pnArray[0];
SwapInt(pnArray, pnArray + size - 1);
h = k - 1;
i = 0;
for (tmp = pnArray[0];h > 0 && 2*i + 1 < size; --h, i = child)
{
child = 2 * i + 1;
if (child >= size-1) break;
if (pnArray[child] > pnArray[child + 1]) ++child;
if (tmp > pnArray[child]) pnArray[i] = pnArray[child];
else break;
pnArray[child] = tmp;
}
return min;
}
void GetKMin(int *pnArray, int size, int k)
{
int i;
MakeMinHeap(pnArray, size);
for (i = 0; i < k; ++i)
{
int min = GetHeapMin(pnArray, size - i, k - i);
cout << min << " ";
}
cout << endl;
}
/**
*µÚÁùÕÂ.Çó500wÄÚµÄÇ׺ÍÊý
*Ç׺ÍÊý: mºÍnΪÇ׺ÍÊý£¬ÔòmµÄÕæÒò×ÓÖ®ºÍΪn, nµÄÕæÒò×ÓÖ®ºÍΪm;
*/
void QinNum(unsigned int n)
{
int i, j;
int *sum = NULL;
if ((sum = (int *)malloc(n*sizeof(int))) == NULL) return;
for (i = 0; i < n; ++i) sum[i] = 1;
for (i = 2; i*2 < n; ++i)
{
j = 2*i;
while (j < n)
{
sum[j] += i;
j += i;
}
}
for (i = 2; i < n; ++i)
{
if (sum[i] > i && sum[i] < n && sum[sum[i]] == i)
{
cout << sum[i] << " " << i << endl;
}
}
free(sum);
}
/**
*µÚÆßÕÂ.ÇóÁ¬Ðø×ÓÊý×éµÄ×î´óºÍ
*
*/
int MaxSum(int *a, int size)
{
int i, sum, tmp;
sum = 0;
tmp = 0;
for (i = 0; i < size; ++i)
{
if (tmp < 0) tmp = a[i];
else tmp += a[i];
if (sum < tmp) sum = tmp;
}
return 0;
}
/**
*µÚ°ËÕÂ.̽ÌÖÐ麯Êý
*/
class Base
{
private:
virtual void f()
{
cout << "Base::f" << endl;
}
};
class Derive : public Base
{
};
typedef void(*Fun)(void);
/**
*µÚ¾ÅÕÂ.Á´±íÎÊÌâ
*1.ÅжÏÁ´±íÊÇ·ñÓл·¡ª¡ª¿ìÂýÁ´±íÖ¸Õë
*2.ÅжÏÁ´±íÊÇ·ñÏཻ
*3.ÕÒ³öÏཻµÄµÚÒ»¸öµã
*
*/
//µÚÊ®¶þ ~Ê®ÎåÕ£ºÖÐÇ©¸ÅÂÊ£¬ IP ·ÃÎÊ´ÎÊý£¬»ØÎĵÈ
//µÚ¶þ²¿·Ö¡¢±éÀú n¸öÔªËØÈ¡³öµÈ ¸ÅÂÊËæ»úÈ¡³öÆäÖÐÖ®Ò»ÔªËØ
//α´úÂë
//Element RandomPick(file):
// Int length = 1;
// While( length <= file.size )
// {
// If( rand() % length == 0)
// Picked = File[length];
// Length++;
// }
// Return picked
/*
int main(int argc, char *argv[])
{
//int anArray[] = {2, 3, 5, 8, 7, 6, 1, 4, 9};
//GetKMin(anArray, 9, 5);
//cout << endl;
// QinNum(5000000);
Derive d;
Fun pFun = (Fun)*((int*)*(int*)(&d)+0);
pFun();
return 0;
}
*/
/*
void CreateSuffixArray(uchar* szText, int L, int** _S, int** _R, int** _T1, int** _T2)
{
int i, h, h2, *T, *S1, *S2, *R, *B;
S1 = *_S; // h½×ºó׺Êý×é
S2 = *_T1; // 2h½×ºó׺Êý×é
R = *_R; // h½×RankÊý×é
B = *_T2; // ij¸öÍ°¿ÕÓà¿Õ¼äβ²¿µÄË÷Òý£¬¼æÈÎ2h½×RankÊý×é
// »¨O(n)µÄʱ¼ä¶Ôh = 1½øÐмÆÊýÅÅÐò
for(i = 0; i < 256; i++) B = 0;
for(i = 0; i < L; i++) B[szText]++;
for(i = 1; i < 256; i++) B += B[i - 1];
for(i = 0; i < L; i++) S1[--B[szText]] = i;
// ¼ÆËãRank(1)£¬ÒòΪ½ö½öÊÇ1½×µÄRank£¬ËùÓÐÓв¢ÁеÄ
for(R[S1[0]] = 0, i = 1; i < L; i++)
{
if(szText[S1] == szText[S1[i - 1]])
R[S1] = R[S1[i - 1]];
else
R[S1] = R[S1[i - 1]] + 1;
}
// log(n)ÌËO(n)µÄ±¶ÔöÅÅÐò
// SA(h) => Rank(h) => SA(2h) => Rank(2h) => ¡
32
33 for(h = 1; h < L && R[S1[L - 1]] < L - 1; h <<= 1)
34 {
35 // ¼ÆËãRank(h)ÏàͬµÄºó׺ÐγɵÄhͰβ²¿µÄË÷Òý
36 // ¼´ÓжàÉÙ¸öºó׺µÄhǰ׺Ïàͬ£¬ËüÃDZ»·ÅÔÚÒ»¸öÍ°ÖÐ
37 for(i = 0; i < L; i++)
38 B[R[S1]] = i;
39
40 // ÇóSA(2h)
41 // ÔÚͬһ¸öhÍ°ÖУ¬ËùÓеĺó׺µÄhǰ׺¿Ï¶¨Ïàͬ£¬
42 // ÄÇô±È½ÏËûÃǵÄ2hǰ׺£¬Ö»Òª±È½ÏÆä2hǰ׺ºó°ëµÄ
43 // ³¤¶ÈΪhµÄ´®¼´¿É£¬¶øÕâ¸ö´®Ç¡Ç¡ÊǺóÃæij¸öºó׺µÄ
44 // hǰ׺£¬ËùÒÔÎÒÃÇÄæÏò±éÀúÓÐÐòµÄSA(h)£¬
45 // ½«S1 ¨C hºÅǰ׺·Åµ½ËüËùÔÚÍ°µÄ×îºóÒ»¸ö¿ÕλÖã¬
46 // ͬʱ£¬Í°Î²Ç°½øÒ»¸öλÖã¬ÕâÑù¼´ÐγÉÁË2hÍ°ÅÅÐò
47 for(i = L ¨C 1; i >= 0; i¨C)
48 if(h <= S1)
49 S2[B[R[S1 - h]]¨C] = S1 ¨C h;
50
51 // ¶ÔÓÚ³¤¶È²»³¬¹ýhµÄ×îºó¼¸¸öºó׺£¬ÓÉÓÚÔÚh½×¶Î
52 // ËüÃÇÿ¸öʵ¼ÊÉ϶¼ÒѾ¶ÀÁ¢·ÖÍ°ÁË(³¤¶ÈΪhµÄÒ²ÊÇ)
53 // ¶øÇÒËûÃǵÄÍ°ÖÐÓÐÇÒ½öÓÐÒ»¸öÔªËØ£¬
54 // ËùÒÔÖ»ÒªÖ±½Ó¸´ÖÆËûÃÇh½×¶ÎµÄSAÖµ¾Í¿ÉÒÔÁË
55 // ͬʱ£¬ÓÉÓÚ²ÉÓùö¶¯Êý×飬ËùÒÔS2ÖС°²ÐÁô¡±ÁË
56 // h/2¸öÓÐЧµÄÊý¾Ý£¬ËùÒÔ×îÖÕÎÒÃÇÖ»Ð踴ÖÆh/2¸öÊý¾Ý
57 for(i = L ¨C h, h2 = L ¨C (h >> 1); i < h2; i++)
58 S2[B[R]] = i;
59
60 T = S1; S1 = S2; S2 = T;
61
62 // ¼ÆËãRank(2h)
63 // 2h½×¶ÎÊÇ·ñÒª·ÖÍ°Ö»Ðè¿´ÏàÁÚÁ½¸ö2hǰ׺ǰºóÁ½°ë
64 // hǰ׺ÊÇ·ñÈ«²¿h½×ÏàµÈ
65 for(B[S1[0]] = 0, i = 1; i < L; i++)
66 {
67 // ÕâÀï²»Óÿ¼ÂÇS1 + h»áÔ½½ç
68 // Èç¹ûi´ïµ½ÁËS1 + hÔ½½çµÄÊýÖµ£¬
69 // ÄÇôǰÃæÒ»¸öÌõ¼þÏÔÈ»²»»áÂú×ãÁË
70 // ÒòΪ´Ëʱiǰ׺¿Ï¶¨ÒѾ¶ÀÁ¢·ÖÍ°ÁË
71 if(R[S1] != R[S1[i - 1]] ||
72 R[S1 + h] != R[S1[i - 1] + h])
73 {
74 B[S1] = B[S1[i - 1]] + 1;
75 }
76 else
77 B[S1] = B[S1[i - 1]];
78 }
79
80 T = B; B = R; R = T;
81 }
82
83 if(*_S != S1)
84 *_S = S1, *_T1 = S2;
85 if(*_R != R)
86 *_R = R, *_T2 = B;
87 }
const int N = 20005;//´®AµÄ×î´ó³¤¶È
const int MAX = 1000100;//´®AµÄ×î´óÖµ
//int n,m,k;
int SA[N], rank[N], height[N], key[N];
int A[N], C[MAX], t1[N+1], t2[N+1];
//±¶Ôö·¨Çósa[]-----´ýÅÅÐòµÄ×Ö·û´®·ÅÔÚr Êý×éÖУ¬r[]ΪÕûÐÍÊý×é, ´Ór[0]µ½r[n-1]£¬³¤¶ÈΪn£¬ÇÒ×î´óֵСÓÚm
//Ô¼¶¨³ýr[n-1]ÍâËùÓеÄr[i]¶¼´óÓÚ0, r[n-1]=0
//½á¹û·ÅÔÚsa Êý×éÖУ¬´Ósa[0]µ½sa[n-1]
//ÏȶÔËùÓкó׺µÄµÚÒ»¸ö×Ö·û½øÐÐÅÅÐò(²ÉÓÃÍÚ¿ÓʽµÄ»ùÊýÅÅÐò,¼´Í³¼Æÿ¸ö×Ö·ûµÄ¸öÊý,ÒÔ±ãÔÚɨÃèʱ×ÜÄܽ«×Ö·û·ÅÈëºÏÊʵÄλÖÃ),·ÅÈësaÖÐ
void da(int n, int m)
{
int i, j, l, s,*t;
int *X = t1, *Y = t2;
memset(C, 0, sizeof(C));
for (i=0; i < n; i++) C[X[i] = A[i]]++;
for (i=1; i < m; i++) C[i] += C[i-1];
for (i=n-1; i >= 0; i--) SA[--C[X[i]]] = i;
for (l=1; l= l) Y[j++] = SA[i] - l;
for (i=0;i=0;i--) SA[--C[key[i]]] = Y[i];
t = X;
X = Y;
Y = t;
X[SA[0]] = j = 0;
for (i=1;i 0)
--k;
if(rank[i] == 0)
height[0] = 0;
else
{
j = SA[rank[i] - 1];
while(A[i+k] == A[j+k])
k++;
height[rank[i]] = k;
}
}
}
void main(void)
{
int i;
//´®A[0]...A[n-1]
for (i = 0; i < 10; ++i)
{
A[i] = 'a' + i;
}
A[3] = 'f';
da(10,1000001); //mµÄ×î´óÖµ²»³¬¹ý1,000,000
for (i = 0; i < 10; ++i)
{
printf("%d ", SA[i]);
}
printf("\n");
calheight(10);
}
*/