PAT「1005 Programming Pattern (35分)」
PAT「1005 Programming Pattern (35分)」
1. 题目
题目链接：PAT「1005 Programming Pattern (35分)」 。
Description
Programmers often have a preference among program constructs. For example, some may prefer if(0==a), while others may prefer if(!a). Analyzing such patterns can help to narrow down a programmer’s identity, which is useful for detecting plagiarism.
Now given some text sampled from someone’s program, can you find the person’s most commonly used pattern of a specific length?
Input Specification:
Each input file contains one test case. For each case, there is one line consisting of the pattern length N (1 \leq N \leq 1048576), followed by one line no less than N and no more than 1048576characters in length, terminated by a carriage return \n. The entire input is case sensitive.
Output Specification:
For each test case, print in one line the length-N substring that occurs most frequently in the input, followed by a space and the number of times it has occurred in the input. If there are multiple such substrings, print the lexicographically smallest one.
Whitespace characters in the input should be printed as they are. Also note that there may be multiple occurrences of the same substring overlapping each other.
Sample Input 1:
4
//A can can can a can.Sample Output 1:
can 4Sample Input 2:
3
int a=~~~~~~~~~~~~~~~~~~~~~0;Sample Output 2:
~~~ 192. 题解
分析
后缀数组实现
这道题可以利用后缀数组解决。求出字符串的后缀数组后，再进一步求出 height 数组。由于 height[i] 表示的是排名为 i 的后缀与排名为 i−1的后缀的最长公共前缀长度，且后缀是根据字典序进行排名的。对于连续的 cnt 个 height[i]>=n，说明某一长度为 n 的子串在字符串中出现了 cnt+1次。而反过来想，对于字符串中长度为 n 的子串，以其首字母为开头的后缀，对应的排名一定是连续的，且排名相邻的后缀的最长公共前缀至少为 n 。因此求出最大的 cnt+1即为最终答案。
代码
后缀数组实现
#include <bits/stdc++.h>
using namespace std;
// 后缀数组
struct SuffixArray {
#ifndef _SA_
#define ll int
#define MAXN 1200000
#define MAXCNT 130
#endif
// 倍增算法计算后缀数组
ll n; // 字符串长度
ll sa[MAXN]; // 后缀数组
ll rk[MAXN]; // 名次数组
ll ssa[MAXN]; // 保留后缀数组
ll srk[MAXN]; // 保留名次数组
ll cnt[MAXCNT]; // 计数数组
ll height[MAXN];// 排名相邻的两个后缀的最长公共前缀
// 倍增法计算后缀数组
void doubling(char *str, ll m) {
ll i, j, k;
// 使用指针方便交换数组
ll *prk = rk, *psrk = srk;
n = strlen(str) + 1;
// 初始基数排序
for(i = 0; i < m; ++i) cnt[i] = 0;
for(i = 0; i < n; ++i) ++cnt[prk[i] = str[i]];
for(i = 1; i < m; ++i) cnt[i] += cnt[i-1];
for(i = n-1; ~i; --i) sa[--cnt[str[i]]] = i;
// 后续基数排序
for(j = 1, k = 1; k < n; j <<= 1, m = k) {
// 根据第二关键字进行基数排序
// 长度不足 j 的子串第二关键字为 0 ，故排到最前面
for(i = n-j, k = 0; i < n; ++i) ssa[k++] = i;
// 长度恰为 j 的子串，其第二关键字必定大于 j
// 即排名小于 j 的上一轮子串必定不能作为此轮子串的第二关键字
for(i = 0; i < n; ++i) if(sa[i] >= j) ssa[k++] = sa[i] - j;
// 根据第一关键字进行基数排序
// 保存此轮排序涉及到的第一关键字，减少不连续内存访问
for(i = 0; i < n; ++i) psrk[i] = prk[ssa[i]];
for(i = 0; i < m; ++i) cnt[i] = 0;
for(i = 0; i < n; ++i) ++cnt[psrk[i]];
for(i = 1; i < m; ++i) cnt[i] += cnt[i-1];
for(i = n-1; ~i; --i) sa[--cnt[psrk[i]]] = ssa[i];
// 计算 rk 数组
swap(prk, psrk);
for(prk[sa[0]] = 0, k = 1, i = 1; i < n; ++i) {
prk[sa[i]] = (psrk[sa[i-1]]==psrk[sa[i]] && psrk[sa[i-1]+j]==psrk[sa[i]+j]) ? k-1 : k++;
}
}
}
// 计算后缀最长公共前缀
void generateHeight(char *str) {
ll i, j, k = 0;
for(i = 0; i < n; ++i) rk[sa[i]] = i;
for(i = 0; i < n; height[rk[i++]] = k)
for(k?k--:0, j = sa[rk[i]-1]; str[i+k] == str[j+k]; ++k);
}
};
int main()
{
int n;
char str[MAXN];
static SuffixArray sa;
scanf("%d", &n);
getchar();
scanf("%[^\n]", str);
sa.doubling(str, MAXCNT-1);
sa.generateHeight(str);
int ans = 0, tans = 0;
int pos = 0;
for(ll i = 0; i < sa.n; ++i) {
if(sa.height[i] >= n) {
++tans;
} else {
tans = 0;
}
if(tans > ans && sa.sa[i]+n <= sa.n) {
ans = tans;
pos = sa.sa[i];
}
}
str[pos+n] = '\0';
printf("%s %d\n", &str[pos], ans+1);
return 0;
}