Musical Themes [USACO]

用的就是后缀数组。最近非常烦躁。谁人定我去或留，定我心中的宇宙。

/*
ID: zhangyc1
LANG: C++
TASK: theme
*/
#include <string>
#include 
#include 
#include 
using namespace std;
#define MAXSIZE 5000
#define MAXDIF 176
int N;
int arrNum[MAXSIZE], arrRank[MAXSIZE], arrSufix[MAXSIZE], arrHeight[MAXSIZE];void prepairData()
{int nPre, nCur;scanf("%d%d", &N, &nPre);for (int i = 0; i < N - 1; i++){scanf("%d", &nCur);arrNum[i] = nCur - nPre + 88;// arrRank[i] : [1, 175]nPre = nCur;}arrNum[N - 1] = 0;// 补一个唯一的0作为序列结尾
}inline bool CmpRank(int a, int b, int nStep)
{return arrRank[a] == arrRank[b] && arrRank[a + nStep] == arrRank[b + nStep];
}void DoubleAdding()
{int arrCount[MAXSIZE], nMaxVal = MAXDIF;int arrRankTemp[MAXSIZE], arrSufix2[MAXSIZE];// 首次基数排序memcpy(arrRank, arrNum, sizeof(int) * N);memset(arrCount, 0, sizeof(arrCount));for (int i = 0; i < N; i++)arrCount[arrRank[i]]++;for (int i = 1; i < nMaxVal; i++)arrCount[i] += arrCount[i - 1];for (int i = N - 1; i >= 0; i--)arrSufix[--arrCount[arrRank[i]]] = i;int nRankNum = 0;for (int nStep = 1; nRankNum < N; nStep *= 2){// 根据上次第一关键字的排序生成本次第二关键字的排序结果int nSorted = 0;for (int i = N - nStep; i < N; i++)arrSufix2[nSorted++] = i;for (int i = 0; i < N; i++)if (arrSufix[i] >= nStep) arrSufix2[nSorted++] = arrSufix[i] - nStep;// 基数排序memset(arrCount, 0, sizeof(arrCount));for (int i = 0; i < N; i++)arrCount[arrRank[i]]++;for (int i = 1; i < nMaxVal; i++)arrCount[i] += arrCount[i - 1];for (int i = N - 1; i >= 0; i--)arrSufix[--arrCount[arrRank[arrSufix2[i]]]] = arrSufix2[i];// 更新ranknRankNum = 1, arrRankTemp[N - 1] = 0;for (int i = 1; i < N; i++){if (CmpRank(arrSufix[i], arrSufix[i - 1], nStep))arrRankTemp[arrSufix[i]] = nRankNum - 1;elsearrRankTemp[arrSufix[i]] = nRankNum++;}memcpy(arrRank, arrRankTemp, sizeof(int) * N);nMaxVal = nRankNum;}
}void CalHeight()
{int k = 0;for (int i = 0; i < N - 1; i++){if (k) k--;for (int j = arrSufix[arrRank[i] - 1]; arrNum[j + k] == arrNum[i + k]; k++);arrHeight[arrRank[i]] = k;}
}bool GroupHeight(int nStep)
{int nSaMax = arrSufix[1], nSaMin = arrSufix[1];int i = 2; // 因为arrHeight[1] = 0, 所以从2开始进入第一组while (i < N){if (arrHeight[i] < nStep){// 因为arrNum数组为后个数减前个数生成的数列。在还原原始序列时是在各元素前插入了个原始值，故sa值相差应大于nStep// 如12345 -- 1111  第3位(从0开始)的1其实是原始的4与3相减生成的，第2位的1是原始的3与2相减生成的，这两个串在原始序列中是相交的。if (nSaMax - nSaMin > nStep)return true;nSaMax = arrSufix[i], nSaMin = arrSufix[i];}else{if (arrSufix[i] > nSaMax)nSaMax = arrSufix[i];if (arrSufix[i] < nSaMin)nSaMin = arrSufix[i];}i++;}return nSaMax - nSaMin > nStep;
}void process()
{DoubleAdding();CalHeight();int nLeft = 4, nRight = (N - 1) / 2;// 不重复的话，末位的0不可能重复，最长为 (N - 1) / 2while (nLeft <= nRight){int nHalf = (nLeft + nRight)/2;if (GroupHeight(nHalf))nLeft = nHalf + 1;elsenRight = nHalf - 1;}if (nRight >= 4)printf("%d\n", nRight + 1);elseprintf("0\n");
}int main(){FILE *streamIn = freopen("theme.in","r",stdin);FILE *streamOut = freopen("theme.out","w",stdout);prepairData();process();fclose(streamIn);fclose(streamOut);return 0;
}

转载于:https://www.cnblogs.com/doublemystery/archive/2013/05/09/3068675.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！